#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int N = 1e9 + 7;
ll fpow(ll a, ll b){
ll ret = 1;
while(b){
if(b & 1) ret = ret * a % N;
a = a * a % N;
b >>= 1;
}
return ret;
}
struct pt{
int x, y, t;
pt(int _x, int _y, int _t) : x(_x), y(_y), t(_t){}
};
bool compx(pt a, pt b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool compy(pt a, pt b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
signed main(void){
fastio;
int n, m, k;
cin>>n>>m>>k;
vector<pt> a;
for(int i = 0; i < k; i++){
int x, y;
char t;
cin>>t>>x>>y;
a.pb(pt(x, y, (t == '-')));
}
if(n == 1 || m == 1){
cout<<fpow(2, n + m - 1 - k)<<"\n";
return 0;
}
sort(a.begin(), a.end(), compx);
vector<int> fixed(2);
map<int, int> st;
for(int i = 0; i < k; i++){
if(st.find(a[i].y) != st.end()){
if(((a[i].x & 1) ^ a[i].t) != st[a[i].y]){
fixed[0] = 1;
break;
}
}
st[a[i].y] = (a[i].x & 1) ^ a[i].t;
}
st.clear();
sort(a.begin(), a.end(), compy);
for(int i = 0; i < k; i++){
if(st.find(a[i].x) != st.end()){
if(((a[i].y & 1) ^ a[i].t) != st[a[i].x]){
fixed[1] = 1;
break;
cout<<0<<"\n";
return 0;
}
}
st[a[i].x] = (a[i].y & 1) ^ a[i].t;
}
if(fixed[0] && fixed[1]){
cout<<0<<"\n";
return 0;
}
set<int> fd[2];
vector<int> bi(2, 1);
for(int i = 0; i < k; i++){
fd[0].insert(a[i].x), fd[1].insert(a[i].y);
bi[((a[i].x + a[i].y) & 1)^ a[i].t] = 0;
}
if(fixed[0]){
cout<<fpow(2, n - fd[0].size())<<"\n";
}
else if(fixed[1]){
cout<<fpow(2, m - fd[1].size())<<"\n";
}
else{
cout<<((fpow(2, m - fd[1].size()) + fpow(2, n - fd[0].size()) - bi[0] - bi[1] + N) % N)<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 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 |
1 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 |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 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 |
1 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 |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
38 ms |
3024 KB |
Output is correct |
17 |
Correct |
34 ms |
2772 KB |
Output is correct |
18 |
Correct |
34 ms |
2772 KB |
Output is correct |
19 |
Correct |
70 ms |
2772 KB |
Output is correct |
20 |
Correct |
81 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 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 |
1 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 |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
38 ms |
3024 KB |
Output is correct |
17 |
Correct |
34 ms |
2772 KB |
Output is correct |
18 |
Correct |
34 ms |
2772 KB |
Output is correct |
19 |
Correct |
70 ms |
2772 KB |
Output is correct |
20 |
Correct |
81 ms |
2772 KB |
Output is correct |
21 |
Correct |
142 ms |
11208 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
35 ms |
3028 KB |
Output is correct |
24 |
Correct |
35 ms |
3280 KB |
Output is correct |
25 |
Correct |
36 ms |
3028 KB |
Output is correct |
26 |
Correct |
48 ms |
5320 KB |
Output is correct |
27 |
Correct |
70 ms |
6228 KB |
Output is correct |
28 |
Correct |
68 ms |
6096 KB |
Output is correct |
29 |
Correct |
122 ms |
14764 KB |
Output is correct |
30 |
Correct |
150 ms |
17676 KB |
Output is correct |