#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
map<int, int> CompX, DecompX, CompY, DecompY;
set<int> valsX, valsY;
array<vector<int>, MAXN> filasX, filasY;
inline int mult(int a, int b){return (a * b) % MOD;}
int exp(int x, int b)
{
if (b < 0) return 0;
if (b == 0) return 1;
if (b % 2) return mult(x, exp(x, b-1));
else return exp(mult(x, x), b/2);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
if (N == 1 || M == 1)
{
cout << max(exp(2, N - K), exp(2, M - K)) << '\n';
return 0;
}
if (K == 0)
{
cout << ((exp(2, N) + exp(2, M)) - 2) % MOD << '\n';
return 0;
}
vector<tuple<char, int, int> > v(K);
int Tipo1 = K+1, Tipo2 = K+1;
for (int i = 0; i < K; i++)
{
auto &[type, x, y] = v[i];
cin >> type >> x >> y;
valsX.insert(x); valsY.insert(y);
if (type == '+') Tipo1 = i;
else Tipo2 = i;
}
int kX = 0, kY = 0;
for (auto x : valsX) CompX[x] = ++kX, DecompX[kX] = x;
for (auto y : valsY) CompY[y] = ++kY, DecompY[kY] = y;
bool TemIntercal = true;
for (int i = 0; i < K; i++)
{
auto [c1, x1, y1] = v[i];
int dist1 = abs(x1 - get<1>(v[Tipo1])) + abs(y1 - get<2>(v[Tipo1]));
int dist2 = abs(x1 - get<1>(v[Tipo2])) + abs(y1 - get<2>(v[Tipo2]));
if ((Tipo1 < K && (dist1 % 2) == (c1 == '+')) || (Tipo2 < K && (dist2 % 2 == (c1 == '-')))) {TemIntercal = false; break;}
}
int respX = 1, respY = 1;
for (auto [c, x, y] : v)
{
//Vou fingir que todos sao +, ent mudo a pos dos - por 1
filasX[CompX[x]].push_back(y + (c == '-'));
filasY[CompY[y]].push_back(x + (c == '-'));
}
//Fila no X, O(K) amortizado
respX = exp(2, N - kX);
for (int i = 1; i <= kX; i++)
{
int distBase = (filasX[i][0] % 2);
for (int j = 1; j < (int)filasX[i].size(); j++) if ((filasX[i][j] % 2) != distBase)
{
respX = 0;
break;
}
}
//Fila no Y, O(K) amortizado
respY = exp(2, M - kY);
for (int i = 1; i <= kY; i++)
{
int distBase = (filasY[i][0] % 2);
for (int j = 1; j < (int)filasY[i].size(); j++) if (filasY[i][j] % 2 != distBase)
{
respY = 0;
break;
}
}
// cerr << respX << " " << respY << " " << TemIntercal << '\n';
if (!TemIntercal) cout << (respX + respY) % MOD << '\n';
else cout << (respX + respY - 1) % MOD << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5016 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5016 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
5204 KB |
Output is correct |
12 |
Correct |
2 ms |
5024 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5280 KB |
Output is correct |
15 |
Correct |
3 ms |
5216 KB |
Output is correct |
16 |
Correct |
49 ms |
10908 KB |
Output is correct |
17 |
Correct |
41 ms |
10912 KB |
Output is correct |
18 |
Correct |
40 ms |
10828 KB |
Output is correct |
19 |
Correct |
41 ms |
10896 KB |
Output is correct |
20 |
Correct |
42 ms |
10776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5016 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
5204 KB |
Output is correct |
12 |
Correct |
2 ms |
5024 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5280 KB |
Output is correct |
15 |
Correct |
3 ms |
5216 KB |
Output is correct |
16 |
Correct |
49 ms |
10908 KB |
Output is correct |
17 |
Correct |
41 ms |
10912 KB |
Output is correct |
18 |
Correct |
40 ms |
10828 KB |
Output is correct |
19 |
Correct |
41 ms |
10896 KB |
Output is correct |
20 |
Correct |
42 ms |
10776 KB |
Output is correct |
21 |
Correct |
232 ms |
33340 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
205 ms |
33316 KB |
Output is correct |
24 |
Correct |
194 ms |
33296 KB |
Output is correct |
25 |
Correct |
217 ms |
33356 KB |
Output is correct |
26 |
Correct |
262 ms |
42644 KB |
Output is correct |
27 |
Correct |
233 ms |
42716 KB |
Output is correct |
28 |
Correct |
245 ms |
42644 KB |
Output is correct |
29 |
Correct |
238 ms |
42668 KB |
Output is correct |
30 |
Correct |
358 ms |
50176 KB |
Output is correct |