Submission #42723

#	Time	Username	Problem	Language	Result	Execution time	Memory
42723		theknife2001	Topovi (COCI15_topovi)	C++14	0 / 120	1 ms	532 KiB

topovi

#include <bits/stdc++.h>
#define ii pair<int , int >
#define se second
#define fi first


using namespace std;
const int N=1e6+55;
ii tree[N*31][2];
map < ii , int > in;
map < int , ii > mx;
map < int , ii > my;
int cnt;
int columns_counter;
int rows_counter;

int newnode()
{
    cnt++;
    return cnt;
}

void add(int node , int i , int x , int val)
{
    if(i<0)
        return ;
    bool bt=(x>>i)&1;
    if(tree[node][bt].fi==0)
        tree[node][bt].fi=newnode();
    tree[node][bt].se+=val;
    add(tree[node][bt].fi,i-1,x,val);
}

int get(int node , int i , int x)
{
    if(i<0)
        return 0;
    bool bt=(x>>i)&1;
    if(i==0)
        return tree[node][bt].se;
    return get(tree[node][bt].fi,i-1,x);
}

int main()
{
    int n,k,q;
    cin>>n>>k>>q;
    int x,y,z;
    for(int i=0;i<k;i++)
    {
        cin>>x>>y>>z;
        in[{x,y}]=z;
        my[y].fi^=z;
        if(my[y].se==0)
            columns_counter++;
        my[y].se++;
        mx[x].fi^=z;
        if(mx[x].se==0)
            rows_counter++;
        mx[x].se++;
    }
    int root=newnode();
    int ans=0;
    for(auto t:my)
    {
        add(root,30,t.se.fi,+1);
    }
    while(1)
        cerr<<1<<endl;
    int x1,y1;
    while(q--)
    {
        cin>>x>>y>>x1>>y1;
        z=in[{x,y}];
        in[{x1,y1}]=z;
        in[{x,y}]=0;
        mx[x].fi^=z;
        mx[x].se--;
        if(!mx[x].se)
            rows_counter--;
        add(root,30,my[y].fi,-1);
        my[y].fi^=z;
        my[y].se--;
        if(!my[y].se)
            columns_counter--;
        else
            add(root,30,my[y].fi,+1);


        if(!mx[x1].se)
            rows_counter++;
        mx[x1].se++;
        mx[x1].fi^=z;
        if(!my[y1].se)
            columns_counter++;
        else
            add(root,30,my[y1].fi,-1);
        my[y1].fi^=z;
        my[y1].se++;
        add(root,30,my[y1].fi,+1);


        ans=rows_counter+columns_counter;
        ans*=n;
        ans-=rows_counter*columns_counter;
        for(auto t:mx)
        {
            ans-=get(root,30,t.se.fi);
        }
        cout<<ans<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 120