초코칩 케이크 - CyberFlower Algorithm

2019 KCPC 초코칩 케이크 (신입생 부문 D번) 코드 제출 url

난이도가 조금 어려워졌습니다. 이제부터는 C++로 설명드리겠습니다.

아이디어성 문제입니다. 쿼리마다 초코를 뿌리고 모든 초코칩 케이크 조각을 검사하는 방법으로는 시간복잡도가 $ O(n^2q) $ 이므로 다른 아이디어를 생각해봐야 합니다.

이 문제를 풀기 위한 아이디어는 다음과 같습니다.

초코가 가장 많이 뿌려진 조각은 (초코가 가장 많이 뿌려진 가로줄의 칸수) * (초코가 가장 많이 뿌려진 세로줄의 칸수) 입니다.
초코가 가장 많이 뿌려진 가로/세로 줄의 칸수는 생각보다 쉽게 구할 수 있습니다.
- 초기에 초코기 기징 많이 뿌려진 칸 수 x,y는 n입니다. (모두 다 0이기 때문에 자명합니다.)
- 가로줄, 세로줄에서 초코칩, max_초코칩을 저장합시다. max_초코칩이 갱신되면 x,y는 1로 바뀝니다.
- max_초코칩에 도달하는 줄이 생긴다면 x,y가 1씩 증가합니다.

#include <bits/stdc++.h>
using namespace std;
const int SZ=30005;
int xx[SZ];
int yy[SZ];
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,q; cin>>n>>q;
    int mx=0,my=0;
    int cx=n,cy=n;
    while(q--){
        int a,b; cin>>a>>b;
        if(a==1){
            xx[b]++;
            if(xx[b]>mx){
                cx=1;
                mx=xx[b];
            }
            else if(xx[b]==mx) cx++;
        }
        else{
            yy[b]++;
            if(yy[b]>my){
                cy=1;
                my=yy[b];
            }
            else if(yy[b]==my) cy++;
        }
        cout<<cx*cy<<'\n';
    }
    return 0;
}

2019 KCPC cake