#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int NMAX = 1e5 + 5;
struct Point {
int x;
int y;
char ch;
};
Point A[NMAX];
int N, M, K;
bool cmp_1 (Point a, Point b) {
return a.x < b.x;
}
bool cmp_2 (Point a, Point b) {
return a.y < b.y;
}
int Value (char ch) {
if (ch == '+') return 1;
return 0;
}
int LogPut (int a, int b) {
if (b == 0) return 1;
if (b == 1) return a;
int val = LogPut(a, b/2);
if (b % 2 == 0) return (1LL * val * val) % MOD;
else return (1LL * val * val * a) % MOD;
}
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> K;
for (int i = 1; i <= K; ++ i )
cin >> A[i].ch >> A[i].x >> A[i].y;
}
int ParalelLines () {
sort(A+1, A+K+1, cmp_1);
int ans = 1;
int Total_Lines = N;
for (int i = 1; i <= K; ++ i ) {
int j = i;
int mat[2][2];
memset(mat, 0, sizeof(mat));
-- Total_Lines;
while (j <= K && A[j].x == A[i].x) ++ j;
-- j;
for (int k = i; k <= j; ++ k )
mat[A[k].y%2][Value(A[k].ch)] ++;
if ((mat[0][0] != 0 && mat[1][0] != 0) || (mat[0][1] != 0 && mat[1][1] != 0) || (mat[0][0] != 0 && mat[0][1] != 0) || (mat[1][0] != 0 && mat[1][1] != 0)) {
ans = 0;
break;
}
i = j;
}
return ans * LogPut(2, Total_Lines);
}
int ParalelColumns () {
sort(A+1, A+K+1, cmp_2);
int ans = 1;
int Total_Columns = M;
for (int i = 1; i <= K; ++ i ) {
int j = i;
int mat[2][2];
memset(mat, 0, sizeof(mat));
-- Total_Columns;
while (j <= K && A[j].y == A[i].y) ++ j;
-- j;
for (int k = i; k <= j; ++ k )
mat[A[k].x%2][Value(A[k].ch)] ++;
if ((mat[0][0] != 0 && mat[1][0] != 0) || (mat[0][1] != 0 && mat[1][1] != 0) || (mat[0][0] != 0 && mat[0][1] != 0) || (mat[1][0] != 0 && mat[1][1] != 0)) {
ans = 0;
break;
}
i = j;
}
return ans * LogPut(2, Total_Columns);
}
int ParalelLinesandColumns () {
int mat[2][2];
memset(mat, 0, sizeof(mat));
for (int i = 1; i <= K; ++ i )
mat[(A[i].x + A[i].y)%2][Value(A[i].ch)]++;
if (K == 0) return 2;
if ((mat[0][0] >= 0 && mat[1][1] >= 0 && mat[1][0] == 0 && mat[0][1] == 0) || (mat[0][1] >= 0 && mat[1][0] >= 0 && mat[0][0] == 0 && mat[1][1] == 0))
return 1;
return 0;
}
int main () {
Read();
int ans = (1LL * ParalelLines() + 1LL * ParalelColumns() - 1LL * ParalelLinesandColumns() + MOD) % MOD;
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
37 ms |
2380 KB |
Output is correct |
17 |
Correct |
35 ms |
2380 KB |
Output is correct |
18 |
Correct |
37 ms |
2428 KB |
Output is correct |
19 |
Correct |
34 ms |
2332 KB |
Output is correct |
20 |
Correct |
39 ms |
2340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
37 ms |
2380 KB |
Output is correct |
17 |
Correct |
35 ms |
2380 KB |
Output is correct |
18 |
Correct |
37 ms |
2428 KB |
Output is correct |
19 |
Correct |
34 ms |
2332 KB |
Output is correct |
20 |
Correct |
39 ms |
2340 KB |
Output is correct |
21 |
Correct |
50 ms |
2804 KB |
Output is correct |
22 |
Correct |
1 ms |
316 KB |
Output is correct |
23 |
Correct |
51 ms |
2764 KB |
Output is correct |
24 |
Correct |
45 ms |
2748 KB |
Output is correct |
25 |
Correct |
43 ms |
2796 KB |
Output is correct |
26 |
Correct |
53 ms |
3156 KB |
Output is correct |
27 |
Correct |
41 ms |
3044 KB |
Output is correct |
28 |
Correct |
44 ms |
3024 KB |
Output is correct |
29 |
Correct |
44 ms |
3012 KB |
Output is correct |
30 |
Correct |
56 ms |
3600 KB |
Output is correct |