페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

입력
35
11R
33L
32D
12L
21U
출력
0
0
0
2
3

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

RL?
U??
?DL

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

RLR
URR
LDL

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


예제2

입력
38
11R
12L
13D
23U
33L
32R
31U
21D
출력
0
2
2
4
4
6
6
9

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

RLD
D?U
URL

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


예제3

입력
413
22R
23R
24D
34D
44L
43L
42U
31D
41R
21L
11D
14L
13D
출력
0
0
0
0
0
0
0
0
11
11
11
11
13

태그

출처

USACO 2024 December Silver

역링크