oj.uz

Submission #251821

# Submission time Handle Problem Language Result Execution time Memory
251821 2020-07-22T10:41:01 Z VEGAnn Topovi (COCI15_topovi) C++14
0 / 120
 1114 ms 40696 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 ans, 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 >> r2 >> c1 >> 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
0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 114 ms 6876 KB Output isn't correct
7 Incorrect 74 ms 5624 KB Output isn't correct
8 Incorrect 75 ms 4600 KB Output isn't correct
9 Incorrect 79 ms 4728 KB Output isn't correct
10 Incorrect 81 ms 5240 KB Output isn't correct
11 Incorrect 1041 ms 40588 KB Output isn't correct
12 Incorrect 997 ms 40544 KB Output isn't correct
13 Incorrect 1006 ms 40568 KB Output isn't correct
14 Incorrect 1073 ms 40572 KB Output isn't correct
15 Incorrect 1010 ms 40568 KB Output isn't correct
16 Incorrect 1020 ms 40608 KB Output isn't correct
17 Incorrect 1114 ms 40696 KB Output isn't correct
18 Incorrect 1008 ms 40564 KB Output isn't correct
19 Incorrect 1006 ms 40568 KB Output isn't correct
20 Incorrect 1006 ms 40568 KB Output isn't correct