USACO 2026 First Contest, Platinum

Problem 3. Pluses and Minuses


Contest has ended.

Log in to allow submissions in analysis mode


Farmer John once painted a rectangular grid on the ground of his pasture. In each cell, he painted either a $+$ or a $−$ (representing $+1$ and $−1$, respectively).

Over time, the paint faded, and Farmer John now remembers the values of only some cells. However, Farmer John does remember one important fact about the original painting:

In every row and every column, the sum of the values in any contiguous subsegment was always between $−1$ and $2$ (inclusive).

As an example, consider the row $\texttt{+ - - +}$. It does not satisfy the condition, since the subsegment $\texttt{+ [ - - ] +}$ has sum $-2$.

However, the row $\texttt{- + + -}$ does satisfy the condition. 

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

Count the number of different grids consistent with Farmer John's memory.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$ ($1\le T\le 100$), the number of independent tests. Each test is specified as follows:

The first line contains $R$, $C$, and $X$ ($1\le R,C\le 5\cdot 10^5$, $0\le X\le \min(10^5,RC)$), meaning that the grid has dimensions $R\times C$ and Farmer John remembers the values of $X$ different cells in the grid.

Then following $X$ lines each contain a character $v\in \{+, -\}$ followed by two integers $r$ and $c$ ($1\le r\le R, 1\le c\le C$), meaning that the value at the $r$th row and $c$th column of the grid is $v$. It is guaranteed that no ordered pair $(r,c)$ appears more than once within a single test.

Additionally, it is guaranteed that neither the sum of $R$ nor the sum of $C$ over all tests exceeds $10^6$, and that the sum of $X$ over all tests does not exceed $2\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output the number of grids on a separate line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
0

SAMPLE INPUT:

1
2 2 0

SAMPLE OUTPUT:

7

Here are the seven grids: 

++
++

++
+-

++
-+

+-
++

+-
-+

-+
++

-+
+-

SCORING:

  • Inputs 3-4: $\min(R,C)=1$ for all tests
  • Inputs 5-6: $R,C\le 10$ for all tests
  • Inputs 7-11: $\sum \max(R,C)^2 \le 10^6$
  • Inputs 12-14: $\sum RC \le 10^6$
  • Inputs 15-22: No additional constraints.

Problem credits: Alex Chen

Contest has ended. No further submissions allowed.