#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
char c;
bool nega=0;
while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){
nega=1;
c=getchar();
}
x=c-48;
while(isdigit(c=getchar())) x=x*10+c-48;
if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "TOPOVI"
ll n;
int k, p;
map <pair <int, int>, int> M;
map <int, int> row_xor;
map <int, int> col_xor;
class trie{
public:
using pointer=trie*;
pointer g[2];
ll count;
trie(){
count=0;
g[0]=g[1]=nullptr;
}
static void insert(pointer root, int x, int factor, int now=0){
root->count+=factor;
if(now==30) return;
if(root->g[bit(x, now)]==nullptr) root->g[bit(x, now)]=new trie();
insert(root->g[bit(x, now)], x, factor, now+1);
}
static ll get(pointer root, int x, int now=0){
if(now==30) return root->count;
if(root->g[bit(x, now)]==nullptr) return 0;
return get(root->g[bit(x, now)], x, now+1);
}
static ll get_pair(pointer A, pointer B, int now=0){
if(now==30) return A->count*B->count;
ll res=0;
if((A->g[0]!=nullptr)&&(B->g[0]!=nullptr)) res+=get_pair(A->g[0], B->g[0], now+1);
if((A->g[1]!=nullptr)&&(B->g[1]!=nullptr)) res+=get_pair(A->g[1], B->g[1], now+1);
return res;
}
};
trie::pointer ROW, COL;
ll ans;
void prepare(){
ROW=new trie();
COL=new trie();
trie::insert(ROW, 0, n-row_xor.size());
trie::insert(COL, 0, n-col_xor.size());
for(auto x: row_xor){
trie::insert(ROW, x.second, 1);
}
for(auto x: col_xor){
trie::insert(COL, x.second, 1);
}
ans=n*n-trie::get_pair(ROW, COL);
}
void pop(int x, int y){
ans+=trie::get(COL, row_xor[x]);
trie::insert(ROW, row_xor[x], -1);
ans+=trie::get(ROW, col_xor[y]);
trie::insert(COL, col_xor[y], -1);
}
void push(int x, int y){
trie::insert(ROW, row_xor[x], 1);
ans-=trie::get(COL, row_xor[x]);
trie::insert(COL, col_xor[y], 1);
ans-=trie::get(ROW, col_xor[y]);
}
int main(){
#ifdef Uiharu
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Uiharu
read(n);
read(k);
read(p);
{
int r, c, x;
FOR(i, 1, k){
read(r);
read(c);
read(x);
row_xor[r]^=x;
col_xor[c]^=x;
M[mp(r, c)]=x;
}
}
prepare();
{
int x, y, u, v;
FOR(i, 1, p){
read(x);
read(y);
read(u);
read(v);
int XOR=M[mp(x, y)];
M.erase(mp(x, y));
pop(x, y);
row_xor[x]^=XOR;
col_xor[y]^=XOR;
push(x, y);
pop(u, v);
row_xor[u]^=XOR;
col_xor[v]^=XOR;
push(u, v);
M[mp(u, v)]=XOR;
writeln(ans);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
201 ms |
4528 KB |
Output is correct |
| 7 |
Correct |
168 ms |
4728 KB |
Output is correct |
| 8 |
Correct |
101 ms |
3704 KB |
Output is correct |
| 9 |
Correct |
110 ms |
3836 KB |
Output is correct |
| 10 |
Correct |
144 ms |
3748 KB |
Output is correct |
| 11 |
Correct |
1605 ms |
30104 KB |
Output is correct |
| 12 |
Correct |
1458 ms |
30200 KB |
Output is correct |
| 13 |
Correct |
1461 ms |
30200 KB |
Output is correct |
| 14 |
Correct |
1411 ms |
30200 KB |
Output is correct |
| 15 |
Correct |
1337 ms |
30200 KB |
Output is correct |
| 16 |
Correct |
1462 ms |
30256 KB |
Output is correct |
| 17 |
Correct |
1500 ms |
30124 KB |
Output is correct |
| 18 |
Correct |
1519 ms |
30300 KB |
Output is correct |
| 19 |
Correct |
1495 ms |
30184 KB |
Output is correct |
| 20 |
Correct |
1446 ms |
30268 KB |
Output is correct |
