Submission #251826

#	Time	Username	Problem	Language	Result	Execution time	Memory
251826		VEGAnn	Topovi (COCI15_topovi)	C++14	120 / 120	1125 ms	27572 KiB

topovi

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
#define ft first
#define sd second
using namespace std;
typedef long long ll;
const int N = 10100;
const int V = 101;
const int C = 22;
const int md = 10007;
set<int> was;
map<i2, int> a;
map<int, int> row, col;
map<int, i2> eq;
ll cans;
int n, k, p;

ll del(int vl){
    if (was.find(vl) != was.end()) return 0;

    was.insert(vl);

    return ll(eq[vl][0]) * ll(eq[vl][1]);
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n >> k >> p;

    for (int i = 0; i < k; i++){
        int r, c, x; cin >> r >> c >> x;

        a[{r, c}] = x;

        row[r] ^= x;
        col[c] ^= x;
    }

    for (auto cr : row)
        eq[cr.sd][0]++;

    for (auto cr : col)
        eq[cr.sd][1]++;

    eq[0][0] += (ll(n) - ll(sz(row)));
    eq[0][1] += (ll(n) - ll(sz(col)));

    for (auto cr : eq)
        cans += ll(cr.sd[0]) * ll(cr.sd[1]);

    for (; p; p--){
        int r1, r2, c1, c2; cin >> r1 >> c1 >> r2 >> c2;

        int vl = a[{r1, c1}];

        a.erase({r1, c1});

        a[{r2, c2}] = vl;

        // update

        int sr1 = row[r1];
        int sr2 = row[r2];
        int sc1 = col[c1];
        int sc2 = col[c2];

        int sR1 = row[r1];
        int sR2 = row[r2];
        int sC1 = col[c1];
        int sC2 = col[c2];

        if (r1 != r2) {
            sR1 ^= vl;
            sR2 ^= vl;
        }

        if (c1 != c2){
            sC1 ^= vl;
            sC2 ^= vl;
        }

        was.clear();

        cans -= del(sr1);
        cans -= del(sr2);
        cans -= del(sc1);
        cans -= del(sc2);
        cans -= del(sR1);
        cans -= del(sR2);
        cans -= del(sC1);
        cans -= del(sC2);

        row[r1] ^= vl;
        col[c1] ^= vl;

        row[r2] ^= vl;
        col[c2] ^= vl;

        eq[sr1][0]--;
        eq[sr2][0]--;
        eq[sR1][0]++;
        eq[sR2][0]++;

        eq[sc1][1]--;
        eq[sc2][1]--;
        eq[sC1][1]++;
        eq[sC2][1]++;

        was.clear();

        cans += del(sR1);
        cans += del(sR2);
        cans += del(sC1);
        cans += del(sC2);
        cans += del(sr1);
        cans += del(sr2);
        cans += del(sc1);
        cans += del(sc2);

        cout << ll(n) * ll(n) - cans << '\n';
    }

    return 0;
}

• Subtask 1: 120 / 120