완전한 승리 — NYPC 2025

$M \times M$ 격자에 $N$ 개의 돌이 놓여있다. 각 격자칸에는 최대 하나의 돌만 놓일 수 있다. 각 돌은 파란색 또는 빨간색이며, 각 색의 돌은 최소 하나씩 존재한다. 이 격자의 $r$ 행 $c$ 열 격자칸을 $(r, c)$ 로 나타내자.

두 돌 $A$ , $B$ 의 좌표가 각각 $(r_A, c_A)$ 와 $(r_B, c_B)$ 일 때, $r_A > r_B$ 와 $c_A > c_B$ 가 모두 성립하면 $A$ 가 $B$ 를 이긴다고 한다.

다음 작업을 원하는 만큼 반복해 임의의 빨간 돌이 임의의 파란 돌을 이기는 완전한 승리 상태를 달성하고 싶다.

원하는 돌 하나를 현재 격자칸에서 다른 원하는 격자칸으로 옮길 수 있다. 이때, 다른 돌이 놓여 있는 격자칸으로는 옮길 수 없다. 또한, 작업은 하나씩 실행해야 하며 $2$ 개 이상의 작업을 동시에 할 수는 없다.

완전한 승리를 달성하기 위해 필요한 최소 작업 횟수를 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 돌의 개수를 나타내는 정수 $N$ 과 좌표 범위를 나타내는 정수 $M$ 이 주어진다. ( $2 \le N \le 300\,000;$ $2 \le M \le 1\,000\,000\,000$ )

그다음 $N$ 개의 줄에 각 돌의 좌표와 색상이 주어진다. 각 줄에는 세 개의 값이 공백으로 구분되어 주어진다. 첫 번째와 두 번째 값은 각각 돌의 행 번호와 열 번호를 나타내는 $1$ 이상 $M$ 이하의 정수이다. 세 번째 값은 영어 대문자 B 또는 R이며, 각각 돌이 파란 색과 빨간 색임을 의미한다.

모든 돌이 놓인 위치는 서로 다르며, 최소 하나의 파란 돌과 빨간 돌이 존재하는 입력만 주어진다.

출력 형식

첫 줄에 완전한 승리를 달성하는 데 필요한 최소 작업 횟수를 출력한다. 단, 달성이 불가능한 경우에는 $-1$ 을 출력한다.

예제 1

입력

7 8 1 1 R 2 4 B 4 1 B 5 6 R 6 7 R 7 1 R 8 2 B

출력

예제 2

입력

4 2 1 1 B 1 2 B 2 1 R 2 2 R

출력

-1

예제 3

입력

2 2 1 1 R 2 2 B

출력

예제 설명

세 번째 예제에서 $(1, 1)$ 에 있는 빨간 돌을 $(1, 2)$ 로 옮기고, $(2, 2)$ 에 있는 파란 돌을 $(1, 1)$ 로 옮긴 후, $(1, 2)$ 에 있는 빨간 돌을 $(2, 2)$ 로 옮기면 완전한 승리를 얻는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 17점

$N \le 10\,000;$ $M \le 100$

종류 2: 9점

$M \le 5\,000$

종류 3: 23점

$M \le 300\,000$

종류 4: 51점

모든 입력 케이스가 주어진다.

해설

먼저 기준 칸 $(r_0, c_0)$ 을 하나 정하면, 완전한 승리 상태란 모든 파란 돌이 $(r \le r_0, c \le c_0)$ 영역 안에 있고, 모든 빨간 돌이 $(r > r_0, c > c_0)$ 영역 안에 들어 있는 상태와 같습니다. 이때 이미 제자리에 놓여 있는 돌은 두 부분으로 나눠 셀 수 있습니다. 하나는 좌하 영역 안에 있는 파란 돌의 수이고, 다른 하나는 우상 영역 안에 있는 빨간 돌의 수입니다. 옮겨야 하는 돌의 개수는 $N$ 에서 이 두 수의 합을 뺀 값이 됩니다. 따라서 어떤 $(r_0, c_0)$ 에서든 이 계산으로 최소 이동 횟수를 얻을 수 있습니다.

다만 여기서 두 가지 예외가 있습니다. 먼저, 좌하 영역과 우상 영역이 빈칸 없이 꽉 차 있는데도 아직 완전한 승리가 되지 않은 경우가 있습니다. 이때는 처음에 돌을 원하는 칸으로 옮길 공간이 없지만, 바깥 영역으로 돌 하나를 빼내어 빈칸을 만든 다음 나머지를 순서대로 옮기고 마지막에 다시 돌을 넣으면 그대로 완전한 승리를 달성할 수 있습니다. 두번째는, 좌하 영역의 크기 자체가 파란 돌 개수보다 작거나 우상 영역의 크기가 빨간 돌 개수보다 작은 경우가 있을 수 있습니다. 이 경우는 칸이 물리적으로 모자라기 때문에 아무리 돌을 이동시켜도 조건을 만족시킬 수 없습니다.

위 예외처리까지 포함하여 모든 $(r_0, c_0)$ 에 대해 나이브하게 구현하면 $\mathcal{O}(M^2 N)$ 이 걸리고, 2차원 누적합을 사용하면 $\mathcal{O}(M^2)$ 까지 줄일 수 있습니다. 하지만 $M$ 이 커지면 이 방식은 불가능하므로, 전체 문제를 해결하기 위해선 최적화가 더 필요합니다.

핵심은 $r_0$ 을 행 단위로 스윕하면서, 각 $c_0$ 에 대해 "이미 제자리에 있는 돌의 수"를 동시에 관리하는 것입니다. 초기 상태에서는 모든 빨간 돌이 우상 영역 조건을 만족하므로 각 빨간 돌은 해당 열보다 작은 모든 $c_0$ 에 1을 더해 줍니다. 이후 $r_0$ 을 하나씩 늘리면서, 현재 행에 있는 파란 돌은 조건을 만족하게 되어 자기 열 이상 모든 $c_0$ 에 1을 더하고, 현재 행에 있는 빨간 돌은 조건에서 빠지므로 자기 열보다 작은 모든 $c_0$ 에서 1을 빼줍니다. 이때마다 특정 $c_0$ 범위의 최댓값을 뽑아야 하므로, 구간 덧셈 업데이트와 구간 최댓값 쿼리를 지원하는 레이지 세그먼트 트리를 사용합니다.

최댓값을 구할 때는 영역의 크기도 확인해야 합니다. 파란 돌은 좌하 영역 안에 모두 들어가야 하고 빨간 돌은 우상 영역 안에 모두 들어가야 하므로, 각각의 영역 크기가 돌 개수 이상이어야 합니다. 즉 $r_0 \cdot c_0 \ge B$ 와 $(M-r_0)(M-c_0) \ge R$ 조건을 동시에 만족해야 합니다. 이를 통해 각 $r_0$ 마다 가능한 $c_0$ 구간 $[L_{r_0}, U_{r_0}]$ 을 계산하고, 세그먼트 트리에서 그 구간의 최댓값만 취합니다. 추가로, $L_{r_0} = U_{r_0}$ 인 경우 좌하 영역과 우상 영역이 빈칸 없이 꽉 차 있을 수 있기 때문에 이를 따로 처리해줘야 합니다.

이 과정을 $r_0=1$ 부터 $M-1$ 까지 반복하며 가능한 값의 최댓값을 $X$ 라고 하면, 최종 답은 $N-X$ 가 됩니다. 만약 어느 $r_0$ 에서도 조건을 만족하는 $c_0$ 구간이 없다면 완전한 승리는 불가능하므로 $-1$ 을 출력합니다. 이 방법을 그대로 구현하면 전체 시간복잡도는 $\mathcal{O}((N + M) \log M)$ 가 됩니다. 다만 열 좌표를 압축하고 실제로 변화가 일어나는 행 근처에서만 갱신과 쿼리를 수행하도록 하면, 불필요한 반복을 줄일 수 있어 전체를 $\mathcal{O}(N \log N)$ 시간에 해결할 수 있습니다.