oj.uz

Submission #251820

# Submission time Handle Problem Language Result Execution time Memory
251820 2020-07-22T10:40:01 Z VEGAnn Topovi (COCI15_topovi) C++14
0 / 120
 1193 ms 40776 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);

        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);

        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 6776 KB Output isn't correct
7 Incorrect 90 ms 5624 KB Output isn't correct
8 Incorrect 60 ms 4600 KB Output isn't correct
9 Incorrect 108 ms 4728 KB Output isn't correct
10 Incorrect 128 ms 5260 KB Output isn't correct
11 Incorrect 1193 ms 40696 KB Output isn't correct
12 Incorrect 1118 ms 40440 KB Output isn't correct
13 Incorrect 1049 ms 40692 KB Output isn't correct
14 Incorrect 1143 ms 40588 KB Output isn't correct
15 Incorrect 1033 ms 40536 KB Output isn't correct
16 Incorrect 1074 ms 40584 KB Output isn't correct
17 Incorrect 1053 ms 40568 KB Output isn't correct
18 Incorrect 1000 ms 40440 KB Output isn't correct
19 Incorrect 1113 ms 40776 KB Output isn't correct
20 Incorrect 1138 ms 40696 KB Output isn't correct