페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8181
서브태스크

2D 컨베이어 벨트 2초 1024MB

문제

농부 존의 우유 공장은 N \times N (1 ≤ N ≤ 1,000) 크기의 격자로 표현될 수 있으며, 각 격자는 컨베이어 벨트를 포함하고 있습니다. 위치 (a, b)는 위에서부터 a번째 행, 왼쪽에서부터 b번째 열에 해당하는 셀을 나타냅니다. 격자의 셀은 5가지 유형 중 하나로 나타낼 수 있습니다:

  • L: 왼쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 왼쪽으로 한 칸씩 이동합니다.

  • R: 오른쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 오른쪽으로 한 칸씩 이동합니다.

  • U: 위쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 위쪽으로 한 칸씩 이동합니다.

  • D: 아래쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 아래쪽으로 한 칸씩 이동합니다.

  • ?: 해당 셀에 아직 컨베이어 벨트가 설치되지 않은 상태를 나타냅니다.

컨베이어 벨트는 격자 바깥으로도 물건을 이동시킬 수 있습니다. 특정 셀 c는 만약 해당 셀에서 시작한 물건이 격자 바깥으로 나가지 못하고 영원히 격자 안에서 움직이는 경우 "사용 불가"로 간주됩니다.

초기에 농부 존은 공장을 건설하지 않았으므로 모든 셀은 ?로 시작합니다. 앞으로 Q일 동안 (1 ≤ Q ≤ 2 ⋅ 10^5), 농부 존은 컨베이어 벨트가 설치되지 않은 셀을 선택하여 컨베이어 벨트를 설치할 예정입니다.

특히, i번째 날에는 농부 존이 위치 (r_i, c_i)에 유형 t_i(t_i ∈ {L, R, U, D})의 컨베이어 벨트를 설치합니다. 위치 (r_i, c_i)에는 이미 컨베이어 벨트가 없다는 것이 보장됩니다.

각 날이 끝날 때마다, 농부 존이 남은 모든 ? 셀에 대해 최적으로 컨베이어 벨트를 설치하여 사용 불가 셀의 최소 수를 계산하는 것을 도와주세요.


입력

첫 번째 줄에는 두 정수 N과 Q가 주어집니다.

다음 Q개의 줄에는 각각 r_i, c_i, t_i가 주어지며, 이는 i번째 날에 농부 존이 (r_i, c_i) 위치에 t_i 유형의 컨베이어 벨트를 설치한다는 것을 나타냅니다.


출력

Q 개의 줄을 출력하며, i번째 줄에는 i번째 날 이후 농부 존이 최적으로 컨베이어 벨트를 설치했을 때 "사용 불가" 셀의 최소 수를 출력합니다.


부분문제

번호 점수 조건
#120점

N≤10

#230점

N≤40

#350점

추가 제약 조건 없음


예제1

입력
3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U
출력
0
0
0
2
3

5일 후 컨베이어 벨트 설치 모습이다.

RL?
U??
?DL

남은 셀들을 효과적으로 설치할 수 있는 하나의 방법은 아래와 같다.

RLR
URR
LDL

이 때, (1,1), (1,2), (2,1)은 사용 불가 셀이 된다.


예제2

입력
3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D
출력
0
2
2
4
4
6
6
9

8일 후 컨베이어 벨트가 설치된 모습은 아래와 같다.

RLD
D?U
URL

중앙에 위치한 셀에는 어떤 벨트가 설치되어도 사용 불가 셀이 된다.


예제3

입력
4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D
출력
0
0
0
0
0
0
0
0
11
11
11
11
13

태그

출처

USACO 2024 December Silver

역링크 공식 문제집만