oj.uz

답안 #98585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98585 2019-02-24T16:43:23 Z JohnTitor Topovi (COCI15_topovi) C++11
120 / 120
 1605 ms 30300 KB 
#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.0 / 120.0

# 결과 실행 시간 메모리 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