oj.uz

Submission #251826

# Submission time Handle Problem Language Result Execution time Memory
251826 2020-07-22T10:46:40 Z VEGAnn Topovi (COCI15_topovi) C++14
120 / 120
 1125 ms 27572 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 101 ms 4088 KB Output is correct
7 Correct 79 ms 3960 KB Output is correct
8 Correct 58 ms 3320 KB Output is correct
9 Correct 63 ms 3576 KB Output is correct
10 Correct 68 ms 3448 KB Output is correct
11 Correct 1125 ms 27572 KB Output is correct
12 Correct 992 ms 27240 KB Output is correct
13 Correct 968 ms 27256 KB Output is correct
14 Correct 938 ms 27368 KB Output is correct
15 Correct 911 ms 27448 KB Output is correct
16 Correct 927 ms 27384 KB Output is correct
17 Correct 905 ms 27260 KB Output is correct
18 Correct 996 ms 27256 KB Output is correct
19 Correct 991 ms 27256 KB Output is correct
20 Correct 911 ms 27200 KB Output is correct