#include <bits/stdc++.h>
using namespace std;
#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;
map<ll,ll> cnt,cnt2;
ll sl,res,n,m,sl2,s[500009],x[500009],y[500009],t1,t2,t3,i,k,xbase,ybase;
char ch;
ll GTN(ll x,ll y) {
if (y<0) return 0;
if (y==0) {
return 1;
}
else {
ll tmp=GTN(x,y/2);
if (y%2==0) {
return (tmp*tmp)%mod;
}
else {
return (((tmp*tmp)%mod)*x)%mod;
}
}
}
int main(){
IO;
cin>>n>>m>>k;
for (i=1;i<=k;i++) {
cin>>ch>>x[i]>>y[i];
if (ch=='+') {
s[i]=1;
}
else {
s[i]=0;
}
}
xbase=-1;
//Try building up x-line
for (i=1;i<=k;i++) {
if (cnt[x[i]]==(s[i]^1^(1&y[i]))+1) {
//Can't build x-line
sl=-1;
break;
}
else if (cnt[x[i]]==0) {
sl++;
cnt[x[i]]=(s[i]^(1&y[i]))+1;
//Checker x-line check
if (xbase==-2) {
//Already nope
}
else if (((cnt[x[i]]-1)^(1&x[i]))==xbase||xbase==-1) {
xbase=(cnt[x[i]]-1)^(1&x[i]);
}
else {
//Can't do checker
xbase=-2;
}
}
}
ybase=-1;
//Try to build y-line
for (i=1;i<=k;i++) {
if (cnt2[y[i]]==(s[i]^1^(1&x[i]))+1) {
//Can't build y-line
sl2=-1;
break;
}
else if (cnt2[y[i]]==0) {
sl2++;
cnt2[y[i]]=(s[i]^(1&x[i]))+1;
//Checker y-line check
if (ybase==-2) {
//Already nope
}
else if (((cnt2[y[i]]-1)^(1&y[i]))==ybase||ybase==-1) {
ybase=(cnt2[y[i]]-1)^(1&y[i]);
}
else {
//Can't do checker
ybase=-2;
}
}
}
if (sl>=0) {
if (xbase>=-1) {
res=(res+GTN(2,n-sl)*GTN(2,m-sl2))%mod;
}
else {
res=(res+GTN(2,n-sl))%mod;
}
}
//cout<<res<<'\n';
if (sl2>=0) {
if (ybase>=-1) {
res=(res+GTN(2,n-sl)*GTN(2,m-sl2))%mod;
}
else {
res=(res+GTN(2,n-sl))%mod;
}
}
//cout<<res<<'\n';
//Both x and y-line
if (sl>=0&&sl2>=0) {
res=(res-GTN(2,n-sl+m-sl2)+mod)%mod;
}
cout<<res<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |