플러스와 마이너스

농부 존은 예전에 목초지 바닥에 직사각형 격자를 그려 놓았다. 각 칸에 그는 \(+\) 또는 \(−\) (각각 \(+1\)과 \(−1\)을 나타냄)를 칠했다.

시간이 지나면서 페인트가 바래서, 농부 존은 이제 일부 칸의 값만 기억한다. 하지만 농부 존은 원래 그림에 대한 한 가지 중요한 사실을 기억하고 있다.

모든 행과 모든 열에서, 임의의 연속 부분 구간의 값의 합은 항상 \(−1\) 이상 \(2\) 이하였다.

예를 들어, 행 \(\texttt{+ - - +}\)를 생각해 보자. 부분 구간 \(\texttt{+ [ - - ] +}\)의 합이 \(-2\)이므로 이 행은 조건을 만족하지 않는다.

반면, 행 \(\texttt{- + + -}\)는 조건을 만족한다.

[ - ] + + -    sum = -1
[ - + ] + -    sum = 0
[ - + + ] -    sum = +1
[ - + + - ]    sum = 0
- [ + ] + -    sum = +1
- [ + + ] -    sum = +2
- [ + + - ]    sum = +1
- + [ + ] -    sum = +1
- + [ + - ]    sum = 0
- + + [ - ]    sum = -1

농부 존의 기억과 일치하는 서로 다른 격자의 개수를 세어라.

Problem credits: Alex Chen

SCORING

• 입력 3-4: 모든 테스트에서 \(\min(R,C)=1\)
• 입력 5-6: 모든 테스트에서 \(R,C\le 10\)
• 입력 7-11: \(\sum \max(R,C)^2 \le 10^6\)
• 입력 12-14: \(\sum RC \le 10^6\)
• 입력 15-22: 추가 제약 없음.

Problem credits: Alex Chen

첫째 줄에 독립적인 테스트의 수 \(T\) (\(1\le T\le 100\))가 주어진다. 각 테스트는 다음과 같이 주어진다.

첫째 줄에 \(R\), \(C\), \(X\) (\(1\le R,C\le 5\cdot 10^5\), \(0\le X\le \min(10^5,RC)\))가 주어지며, 이는 격자의 크기가 \(R\times C\)이고 농부 존이 격자에서 서로 다른 \(X\)개 칸의 값을 기억함을 의미한다.

다음 \(X\)개의 줄에 각각 문자 \(v\in \{+, -\}\)와 두 정수 \(r\), \(c\) (\(1\le r\le R, 1\le c\le C\))가 주어지며, 이는 격자의 \(r\)번째 행, \(c\)번째 열의 값이 \(v\)임을 의미한다. 하나의 테스트 안에서 어떤 순서쌍 \((r,c)\)도 두 번 이상 나타나지 않음이 보장된다.

또한, 모든 테스트에 걸친 \(R\)의 합과 \(C\)의 합이 각각 \(10^6\)을 넘지 않고, 모든 테스트에 걸친 \(X\)의 합이 \(2\cdot 10^5\)를 넘지 않음이 보장된다.

각 테스트에 대해, 격자의 개수를 한 줄에 하나씩 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Platinum