Submission #1110957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110957		jklepec	Topovi (COCI15_topovi)	C++11	120 / 120	1204 ms	65536 KiB

topovi

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define pb push_back
#define INF 200000000000000000
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
typedef long long ll;
const ll P = 10007;
const ll mod = 1e9 + 7;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int M = 1e5 + 5;
map<int,int> col, row, calc, calr, cntx, cnty;
map<pair<int,int>,int> mp;
ll cnt1 = 0, cnt2 = 0;
int main()
{
 
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    int n, k, p; cin >> n >> k >> p;
    ll tot = 0;
    set<int> stx, sty;
    for(int i = 0; i < k; i++) {
        int x, y, val; cin >> x >> y >> val;
        stx.insert(x); sty.insert(y);
        mp[{x,y}] = val;
        if(cntx[x] == 0) {
            tot += (n - cnt2);
            cnt1++;
        }
        cntx[x]++;
        if(cnty[y] == 0) {
            tot += (n - cnt1);
            cnt2++;
        }
        cnty[y]++;
        calr[x] ^= val;
        calc[y] ^= val;
    }
    for(auto i : stx) {
        row[calr[i]]++;
    }
    for(auto i : sty) {
        col[calc[i]]++;
    }
    for(auto i : stx) {
        tot -= col[calr[i]];
    }
    while(p--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
      /*  cntx[x1]--;
        if(cntx[x1] == 0) {
            tot -= (n - cnt2);
            cnt1--;
        }
        cnty[y1]--;
        if(cnty[y1] == 0) {
            tot -= (n - cnt1);
            cnt2--;
        }
      //  cout << tot << 'P' << endl;*/
        tot += col[calr[x1]];
        tot += row[calc[y1]];
 
        row[calr[x1]]--;
        col[calc[y1]]--;
 
        calr[x1] ^= mp[{x1,y1}];
        calc[y1] ^= mp[{x1,y1}];
 
        row[calr[x1]]++;
        col[calc[y1]]++;
 
        tot -= col[calr[x1]];
        tot -= row[calc[y1]];
 
        bool ok1 = 0, ok2 = 0;
         if(cntx[x2] == 0) {
            tot += (n - cnt2);
            cnt1++;
        }
        else {
            ok1 = 1;
            tot += col[calr[x2]];
 
        }
        cntx[x2]++;
 
        if(cnty[y2] == 0) {
            tot += (n - cnt1);
            cnt2++;
        }
        else {
            ok2 = 1;
           tot += row[calc[y2]];
 
           col[calc[y2]]--;
        }
        if(ok1 == 1) row[calr[x2]]--;
 
        cnty[y2]++;
        calr[x2] ^= mp[{x1,y1}];
        calc[y2] ^= mp[{x1,y1}];
 
        row[calr[x2]]++;
        col[calc[y2]]++;
 
        tot -= row[calc[y2]];
        tot -= col[calr[x2]];
 
        if(calc[y2] == calr[x2] && ok1 == 0 && ok2 == 0) {
            tot += 1;
        }
        else if(calc[y2] == calr[x2] && ok1 == 1 && ok2 == 0) {
            tot++;
        }
        else if(calc[y2] == calr[x2] && ok1 == 0 && ok2 == 1) {
            tot++;
        }
       mp[{x2,y2}] = mp[{x1,y1}];
       mp[{x1,y1}] = 0;
       cout << tot - ( (ll) (n - cnt2) * row[0] + (ll) (n - cnt1) * col[0] ) << endl;
    }
    return 0;
}

• Subtask 1: 120 / 120