#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
map<int, int> r, c;
ll mop(ll a, ll p) {
ll ans = 1;
for (;p != 0ll;p >>= 1ll, a = a * a % MOD) {
if (p & 1ll) ans = ans * a % MOD;
}
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
if (n == 1) {
cout << mop(2, m - k) << '\n';
return 0;
}
if (m == 1) {
cout << mop(2, n - k) << '\n';
return 0;
}
int cr = n, cc = m;
int in0 = 1, in1 = 1;
while (k--) {
char C;
int x, y;
cin >> C >> x >> y;
int st = C == '+';
int rst = (y & 1) ^ st, cst = (x & 1) ^ st;
if ((x & 1) ^ (y & 1) ^ st) in0 = 0;
else in1 = 0;
// row
if (cr != -1) {
if (!r.count(x)) r[x] = rst, cr--;
else if (r[x] != rst) cr = -1;
}
// col
if (cc != -1) {
if (!c.count(y)) c[y] = cst, cc--;
else if (c[y] != cst) cc = -1;
}
}
// handle interception cases
if (cr == -1 && cc == -1) {
cout << 0 << '\n';
return 0;
}
ll ans = 0;
if (cr != -1) ans = (ans + mop(2, cr)) % MOD;
if (cc != -1) ans = (ans + mop(2, cc)) % MOD;
cout << (ans - in0 - in1 + MOD) % MOD << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
468 KB |
Output is correct |
17 |
Correct |
9 ms |
348 KB |
Output is correct |
18 |
Correct |
10 ms |
456 KB |
Output is correct |
19 |
Correct |
25 ms |
348 KB |
Output is correct |
20 |
Correct |
27 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
468 KB |
Output is correct |
17 |
Correct |
9 ms |
348 KB |
Output is correct |
18 |
Correct |
10 ms |
456 KB |
Output is correct |
19 |
Correct |
25 ms |
348 KB |
Output is correct |
20 |
Correct |
27 ms |
344 KB |
Output is correct |
21 |
Correct |
74 ms |
5976 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
11 ms |
348 KB |
Output is correct |
24 |
Correct |
11 ms |
508 KB |
Output is correct |
25 |
Correct |
11 ms |
524 KB |
Output is correct |
26 |
Correct |
39 ms |
4280 KB |
Output is correct |
27 |
Correct |
39 ms |
4432 KB |
Output is correct |
28 |
Correct |
59 ms |
6360 KB |
Output is correct |
29 |
Correct |
69 ms |
8272 KB |
Output is correct |
30 |
Correct |
88 ms |
9808 KB |
Output is correct |