#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define task "TOPOVI"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
//brute
const int N=100010;
int n,k,p;
int val[N];
ii pos[N];
struct{int x1,y1,x2,y2;}query[N];
vector<int> x,y;
int xv[N],yv[N],ox[N],oy[N];
map<ii,int> mp;
int posin(const vector<int>&x,int y)
{
return lower_bound(all(x),y)-x.begin()+1;
}
void build()
{
forinc(t,1,k)
{
int i=posin(x,pos[t].fi);
int j=posin(y,pos[t].se);
xv[i]^=val[t];
yv[j]^=val[t];
ox[i]++;
oy[j]++;
mp[{i,j}]=t;
}
}
void change(int t)
{
int i1=posin(x,query[t].x1);
int j1=posin(y,query[t].y1);
int i2=posin(x,query[t].x2);
int j2=posin(y,query[t].y2);
int id=mp[{i1,j1}];
xv[i1]^=val[id];
yv[j1]^=val[id];
ox[i1]--,oy[j1]--;
xv[i2]^=val[id];
yv[j2]^=val[id];
ox[i2]++,oy[j2]++;
mp[{i2,j2}]=id;
mp[{i1,j1}]=0;
}
int solve()
{
int ret=n*n,cx=0,cy=0;
forinc(i,1,x.size()) cx+=(!!xv[i]);
forinc(i,1,y.size()) cy+=(!!yv[i]);
ret-=(n-cx)*(n-cy);
forinc(i,1,x.size()) if(ox[i])
{
forinc(j,1,y.size()) if(oy[j] && xv[i]==yv[j])
ret--;
}
return ret;
}
main()
{
//freopen(task".inp","r",stdin);
n=in,k=in,p=in;
forinc(i,1,k) pos[i]={in,in},val[i]=in;
forinc(i,1,p) query[i]={in,in,in,in};
forinc(i,1,k)
{
x.pb(pos[i].fi);
y.pb(pos[i].se);
}
forinc(i,1,p)
{
x.pb(query[i].x1);
x.pb(query[i].x2);
y.pb(query[i].y1);
y.pb(query[i].y2);
}
sort(all(x)),x.erase(unique(all(x)),x.end());
sort(all(y)),y.erase(unique(all(y)),y.end());
build();
forinc(i,1,p)
{
change(i);
cout<<solve()<<"\n";
}
}
Compilation message
topovi.cpp:95:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 6 |
Execution timed out |
2020 ms |
2292 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2027 ms |
2556 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2015 ms |
2176 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2053 ms |
2164 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2049 ms |
2044 KB |
Time limit exceeded |
| 11 |
Runtime error |
230 ms |
26300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
130 ms |
15440 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
2087 ms |
13240 KB |
Time limit exceeded |
| 14 |
Runtime error |
163 ms |
19024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
176 ms |
16636 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
128 ms |
14168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
147 ms |
17196 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Execution timed out |
2040 ms |
13464 KB |
Time limit exceeded |
| 19 |
Runtime error |
129 ms |
15544 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Execution timed out |
2039 ms |
13264 KB |
Time limit exceeded |
