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

#8863
서브태스크

플러스와 마이너스 1s 1024MB

문제

Farmer John은 예전에 자신의 목초지 바닥에 직사각형 격자를 그렸습니다. 각 칸에는 + 또는 − (각각 +1과 −1을 나타냄) 중 하나를 그렸습니다.

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

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

예를 들어, 행 + - - +를 생각해 봅시다. 부분 구간 + [ - - ] +의 합이 −2이므로 이 행은 조건을 만족하지 않습니다.

반면, 행 - + + -는 조건을 만족합니다.

[ - ] + + - \, \, \, \, \, \, \, 합 = -1

[ - + ] + - \, \, \, \, \, \, \, 합 = 0

[ - + + ] - \, \, \, \, \, \, \, 합 = +1

[ - + + - ] \, \, \, \, \, \, \, 합 = 0

- [ + ] + - \, \, \, \, \, \, \, 합 = +1

- [ + + ] - \, \, \, \, \, \, \, \, \, 합 = +2

- [ + + - ] \, \, \, \, \, \, \, 합 = +1

- + [ + ] - \, \, \, \, \, \, \, 합 = +1

- + [ + - ] \, \, \, \, \, \, \, 합 = 0

- + + [ - ] \, \, \, \, \, \, \, 합 = -1

Farmer John의 기억과 일치하는 서로 다른 격자의 개수를 구하세요.


입력

첫 번째 줄에는 독립적인 테스트의 개수 T (1≤T≤100)가 주어집니다. 각 테스트는 다음과 같이 주어집니다:

첫 번째 줄에는 R, C, X (1≤R,C≤5⋅10^5, 0≤X≤min(10^5,RC))가 주어지며, 이는 격자의 크기가 R×C이고 존 농부가 격자 내 X개의 서로 다른 칸의 값을 기억하고 있음을 의미합니다.

그 다음 X개의 줄에는 각각 문자 v∈\{+,−\}와 두 정수 r, c (1≤r≤R, 1≤c≤C)가 주어지며, 이는 격자의 r번째 행, c번째 열의 값이 v임을 의미합니다. 하나의 테스트 내에서 순서쌍 (r,c)가 두 번 이상 나타나지 않음이 보장됩니다.

또한, 모든 테스트에 대한 R의 합과 C의 합이 각각 10^6을 초과하지 않으며, 모든 테스트에 대한 X의 합이 2⋅10^5을 초과하지 않음이 보장됩니다.


출력

각 테스트마다 격자의 수를 별도의 줄에 출력합니다.


부분문제

번호 점수 조건
#110점

모든 테스트에 대해 min(R,C)=1

#210점

모든 테스트에 대해 R,C≤10

#320점

∑max(R,C)^2≤10^6

#420점

∑RC≤10^6

#540점

추가 제약 조건 없음


예제 #1

2
1 3 3
+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2
1
0

예제 #2

1
2 2 0
7

다음은 7개의 그리드입니다:

++

++

++

+-

++

-+

+-

++

+-

-+

-+

++

-+

+-


출처

USACO 2026 First Contest, Platinum

로그인해야 코드를 작성할 수 있어요.