Submission #98585

#	Time	Username	Problem	Language	Result	Execution time	Memory
98585		JohnTitor	Topovi (COCI15_topovi)	C++11	120 / 120	1605 ms	30300 KiB

topovi

#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);
        }
    }
}

• Subtask 1: 120 / 120