Submission #153956

#	Time	Username	Problem	Language	Result	Execution time	Memory
153956		nicolaalexandra	Topovi (COCI15_topovi)	C++14	120 / 120	1997 ms	32060 KiB

topovi

#include <iostream>
#include <set>
#include <map>
#define INF 2000000000
using namespace std;

int n,k,q,sol,l,c,val,l1,l2,c1,c2,i;

map <int,int> dp_l,dp_c,fr_l,fr_c;
map <pair<int,int>,int> value;
int main (){

    cin>>n>>k>>q;
    /// numar cate casute au valorea 0
    long long sol = 1LL*n*n;
    fr_l[0] = n, fr_c[0] = n;
    for (i=1;i<=k;i++){
        cin>>l>>c>>val;
        int val_lin = dp_l[l], val_col = dp_c[c];

        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l] ^= val, dp_c[c] ^= val;
        val_lin = dp_l[l], val_col = dp_c[c];
        fr_l[val_lin]++, fr_c[val_col]++; /// tin minte frecv pt linii si coloane


        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        value[make_pair(l,c)] = val;
    }

    for (;q--;){
        cin>>l1>>c1>>l2>>c2;
        int val = value[make_pair(l1,c1)];
        /// sterg
        int val_lin = dp_l[l1], val_col = dp_c[c1];
        value.erase(make_pair(l1,c1));
        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l1] ^= val, dp_c[c1] ^= val;
        val_lin = dp_l[l1], val_col = dp_c[c1];
        fr_l[val_lin]++, fr_c[val_col]++;

        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        /// adaug
        value[make_pair(l2,c2)] = val;
        val_lin = dp_l[l2], val_col = dp_c[c2];
        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l2] ^= val, dp_c[c2] ^= val;
        val_lin = dp_l[l2], val_col = dp_c[c2];
        fr_l[val_lin]++, fr_c[val_col]++;

        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        cout<<1LL*n*n-sol<<"\n";
    }


    return 0;
}

• Subtask 1: 120 / 120