#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())
const int mod = 1e9 + 7;
int power(int a, int n) {
int res = 1;
while (n) {
if (n % 2) {
(res *= a) %= mod;
}
(a *= a) %= mod;
n /= 2;
}
return res;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> x(k), y(k), t(k);
rep(i, k) {
char c;
cin >> c >> x[i] >> y[i];
t[i] = (c == '+');
--x[i], --y[i];
}
if (k == 0){
cout << (power(2, n) + power(2, m) - 2 + 5 * mod) % mod;
return;
}
if (n == 1 || m == 1) {
cout << power(2, n * m - k);
return;
}
bool need = 0;
int res = 0;
auto add = [&] () -> void {
map<int, int> mp;
rep(i, k) {
int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));
if (mp.find(y[i]) != mp.end() && mp[y[i]] != type) {
return;
}
mp[y[i]] = type;
}
(res += power(2, m - sz(mp))) %= mod;
bool del = 1;
int prv = -1, prv_type = -1;
for (auto &[y, type] : mp) {
if (prv != -1) {
del &= (y - prv) % 2 == ((type == prv_type) ^ 1);
}
prv = y;
prv_type = type;
}
need |= del;
};
add();
rep(i, k) {
int xx = x[i];
int yy = y[i];
y[i] = n - 1 - xx;
x[i] = yy;
}
swap(n, m);
add();
if (need) {
res -= 1;
if (res < 0) {
res += mod;
}
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
plusminus.cpp: In lambda function:
plusminus.cpp:58:50: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
58 | int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
16 ms |
2644 KB |
Output is correct |
17 |
Correct |
15 ms |
2684 KB |
Output is correct |
18 |
Correct |
15 ms |
2644 KB |
Output is correct |
19 |
Correct |
50 ms |
2728 KB |
Output is correct |
20 |
Correct |
44 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
16 ms |
2644 KB |
Output is correct |
17 |
Correct |
15 ms |
2684 KB |
Output is correct |
18 |
Correct |
15 ms |
2644 KB |
Output is correct |
19 |
Correct |
50 ms |
2728 KB |
Output is correct |
20 |
Correct |
44 ms |
2644 KB |
Output is correct |
21 |
Correct |
101 ms |
6288 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
17 ms |
2644 KB |
Output is correct |
24 |
Correct |
20 ms |
2644 KB |
Output is correct |
25 |
Correct |
17 ms |
2664 KB |
Output is correct |
26 |
Correct |
50 ms |
6072 KB |
Output is correct |
27 |
Correct |
49 ms |
5428 KB |
Output is correct |
28 |
Correct |
69 ms |
6332 KB |
Output is correct |
29 |
Correct |
120 ms |
7464 KB |
Output is correct |
30 |
Correct |
141 ms |
8980 KB |
Output is correct |