R02705
전광판
골드 I레이팅
의견: 0
설명
\(N \times N\) 크기의 전광판이 있다. 전광판의 각 칸은 켜짐 또는 꺼짐 중 한 상태를 가지며, 처음에는 모든 칸이 꺼져 있다.
이제 \(Q\)개의 명령을 주어진 순서대로 처리한다. 각 명령은 다음 두 종류 중 하나이다.
- 유형 1: 정수 \(R\)이 주어진다. 위에서 \(R\)번째 행에 있는 모든 칸을 켠다 (이미 켜져 있던 칸은 그대로 켜져 있다).
- 유형 2: 정수 \(C\)가 주어진다. 왼쪽에서 \(C\)번째 열에 있는 모든 칸을 끈다 (이미 꺼져 있던 칸은 그대로 꺼져 있다).
각 명령을 처리한 직후, 전광판에서 현재 켜져 있는 칸의 개수를 출력하시오.
제약
- \(1 \le N,\ Q \le 3 \times 10^5\)
- 유형 1 명령에서는 \(1 \le R \le N\)이다.
- 유형 2 명령에서는 \(1 \le C \le N\)이다.
- 입력으로 주어지는 모든 값은 정수이다.
입력 형식
첫째 줄에 전광판의 한 변의 길이 \(N\)과 명령의 개수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 각 명령이 순서대로 주어진다. 각 명령은 다음 두 형식 중 하나이다.
1 R— 위에서 \(R\)번째 행의 모든 칸을 켜는 유형 1 명령2 C— 왼쪽에서 \(C\)번째 열의 모든 칸을 끄는 유형 2 명령
출력 형식
총 \(Q\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 명령을 처리한 직후 전광판에서 켜져 있는 칸의 개수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(1 \le N, Q \le 2\,000\) |
Subtask 2 | 30점 | \(1 \le N, Q \le 10^5\) |
Subtask 3 | 50점 | 추가 제한이 없다. |
예제 1
입력
4 5
1 2
1 4
2 3
1 2
2 1출력
4
8
6
7
5설명
\(4 \times 4\) 전광판에서 명령을 차례로 처리한다 (. = 꺼짐, # = 켜짐).
1 2— 2번째 행을 켠다. 켜진 칸: \(4\)개.1 4— 4번째 행을 켠다. 켜진 칸: \(8\)개.2 3— 3번째 열을 끈다. 2·4번째 행의 3번째 열 칸이 꺼져 켜진 칸이 \(6\)개가 된다.1 2— 2번째 행을 다시 켠다. 방금 꺼졌던 2번째 행 3번째 열 칸이 다시 켜져 \(7\)개가 된다.2 1— 1번째 열을 끈다. 2·4번째 행의 1번째 열 칸이 꺼져 \(5\)개가 된다.
예제 2
입력
100000 1
2 1출력
0설명
아직 아무 칸도 켜져 있지 않은 상태에서 어떤 열을 끄더라도 켜진 칸의 수는 여전히 \(0\)이다.
문제 정보
rip 작성
출처 지정되지 않음
태그
평가 및 의견
전광판
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
전광판
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기