시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 512 MB | 172 | 89 | 74 | 54.015% |
2021년도 이제 얼마 남지 않았다. 희노애락의 연속이었던 2021년의 이른 회고를 위해 이하는 직사각형 모양의 케이크를 구매했고 이제 언박싱만을 기다리고 있다. 대칭과 일관성을 중시하는 이하는 케이크를 위에서 볼 때 가로 $n$줄, 세로 $n$줄로 총 $n^2$개의 정사각형 조각이 되도록 제작주문했다. 케이크 상자를 열어보니 이하가 원한 대로 똑같은 크기의 정사각형 조각이 많이 있다. 그러나 이하는 주문할 때 토핑까지는 신경쓰지 못해서, 모든 조각 위에는 아무런 장식이 없어 밋밋해보이기까지 한다. 이하는 맛과 비주얼을 위해 케이크에 초코칩을 다음과 같이 $q$번 올려 장식을 하려 한다.
이하는 초코칩이 아주 많기 때문에, 중간에 초코칩을 올리다 모자라는 일은 없다. 이 수많은 초코칩을 한땀한땀 올리는 이하는 원초적이며 본질적인 의문에 빠지지 않을 수 없었다. 매번 초코칩을 줄에 올릴 때마다 초코칩이 가장 많이 있는 조각의 개수는 어떻게 변할까? 이하가 초코칩을 장인정신으로 올리고 있는 동안 이하의 궁금증을 대신 해결해보자.
첫 번째 줄에 두 정수 $n$, $q$가 공백으로 구분되어 주어진다. $(1 \leq n \leq 30,000, 1 \leq q \leq 100,000)$
$n$은 가로줄과 세로줄의 개수이며, $q$는 장식 횟수이다.
이후로 $q$개의 줄에 두 정수 $t$, $a$가 공백으로 구분되어 주어진다. ($1 \leq t \leq 2,\ 1 \leq a \leq n$)
$t$ 가 $1$이면 $a$번째 가로줄에, $2$이면 $a$번째 세로줄에 있는 모든 조각에 초코칩을 $1$개씩 올린다. 한 번 올린 초코칩은 계속 유지된다.
각 줄마다 매 번 장식을 한 이후 케이크에 초코칩이 가장 많이 있는 조각의 개수를 출력한다.
3 2 1 1 1 3
3 6
첫 번째 장식은 첫 번째 가로줄에 초코칩을 뿌린다, 3개의 조각에 초코칩이 1개, 6개의 조각에 초코칩이 0개 있어 초코칩이 가장 많이 있는 조각은 3개이다.
두 번째 장식까지 뿌리고 나면 6개의 조각에 초코칩이 1개, 나머지 3개의 조각에 초코칩이 0개 있어 초코칩이 가장 많이 있는 조각은 6개이다.
1 3 1 1 2 1 1 1
1 1 1
조각이 1개밖에 없으므로, 장식과 상관없이 초코칩이 가장 많이 있는 조각은 1개이다.
4 5 1 1 1 4 2 3 1 4 2 2
4 8 2 1 2