(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
박한별과 은하는 코드포스에서 다음 대회가 열리기까지 남는 시간 동안 색칠놀이를 하기로 했다.
색칠할 그림은 가로 m, 세로 n의 격자 모양으로, 가로줄에는 1부터 n까지, 세로줄에는 1부터 m까지의 번호가 붙어 있다. 위에서 a번째, 왼쪽에서 b번째 칸은 (a, b)로 나타낸다.
그림은 처음에 체크무늬로 색칠되어 있다. 즉, (a, b)는 a + b가 짝수일 때 흰색, 홀수일 때 검은색이다.
박한별은 질서 성향이라서 단순한 그림을 좋아한다. 어떤 정수 t에 대해 (a, b)를 a < t이면 검은색, 그렇지 않으면 흰색으로 만들기 위해 덧칠해야 하는 칸 수를 생각할 수 있다. 이 덧칠해야 하는 칸 수의 최솟값을 색칠된 그림의 복잡도라고 정의한다. 즉, 그림에 적절히 길이 m의 가로줄을 그어 위아래의 두 부분으로 나누고, 그 위의 모든 칸을 검은색, 아래의 모든 칸을 흰색으로 칠하는 데 필요한 최소 칸 수라고 할 수 있다.
은하는 혼돈 성향이라서 주기적으로 색칠된 칸 중 하나를 반대 색으로 덧칠한다. 즉, 검은색은 흰색으로, 흰색은 검은색으로 덧칠한다. 박한별은 은하가 덧칠을 할 때마다 바뀐 그림의 복잡도를 계산하고 싶어 한다. 은하는 덧칠을 총 q번 하려고 하며, i번째로 덧칠할 칸은 (ai, bi)이다.
박한별은 은하가 덧칠을 하는 속도를 따라잡지 못하고 있다. 박한별을 도와주자!
입력
첫째 줄에 그림의 크기 n과 m이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 200,000, 1 ≤ m ≤ 10)
둘째 줄에 은하가 덧칠을 하는 횟수 q가 주어진다. (1 ≤ q ≤ 200,000)
셋째 줄부터 q줄에 걸쳐 은하가 i번째로 덧칠하는 칸의 좌표 ai와 bi가 공백으로 구분되어 주어진다. (1 ≤ ai ≤ n, 1 ≤ bi ≤ m)
dlaud5379 1년 전
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
박한별과 은하는 코드포스에서 다음 대회가 열리기까지 남는 시간 동안 색칠놀이를 하기로 했다.
색칠할 그림은 가로 m, 세로 n의 격자 모양으로, 가로줄에는 1부터 n까지, 세로줄에는 1부터 m까지의 번호가 붙어 있다. 위에서 a번째, 왼쪽에서 b번째 칸은 (a, b)로 나타낸다.
그림은 처음에 체크무늬로 색칠되어 있다. 즉, (a, b)는 a + b가 짝수일 때 흰색, 홀수일 때 검은색이다.
박한별은 질서 성향이라서 단순한 그림을 좋아한다. 어떤 정수 t에 대해 (a, b)를 a < t이면 검은색, 그렇지 않으면 흰색으로 만들기 위해 덧칠해야 하는 칸 수를 생각할 수 있다. 이 덧칠해야 하는 칸 수의 최솟값을 색칠된 그림의 복잡도라고 정의한다. 즉, 그림에 적절히 길이 m의 가로줄을 그어 위아래의 두 부분으로 나누고, 그 위의 모든 칸을 검은색, 아래의 모든 칸을 흰색으로 칠하는 데 필요한 최소 칸 수라고 할 수 있다.
은하는 혼돈 성향이라서 주기적으로 색칠된 칸 중 하나를 반대 색으로 덧칠한다. 즉, 검은색은 흰색으로, 흰색은 검은색으로 덧칠한다. 박한별은 은하가 덧칠을 할 때마다 바뀐 그림의 복잡도를 계산하고 싶어 한다. 은하는 덧칠을 총 q번 하려고 하며, i번째로 덧칠할 칸은 (ai, bi)이다.
박한별은 은하가 덧칠을 하는 속도를 따라잡지 못하고 있다. 박한별을 도와주자!
입력
첫째 줄에 그림의 크기 n과 m이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 200,000, 1 ≤ m ≤ 10)
둘째 줄에 은하가 덧칠을 하는 횟수 q가 주어진다. (1 ≤ q ≤ 200,000)
셋째 줄부터 q줄에 걸쳐 은하가 i번째로 덧칠하는 칸의 좌표 ai와 bi가 공백으로 구분되어 주어진다. (1 ≤ ai ≤ n, 1 ≤ bi ≤ m)
출력
q줄에 걸쳐 은하가 덧칠을 할 때마다 덧칠을 하고 난 뒤에 그림의 복잡도를 출력한다.