oj.uz

Submission #251819

# Submission time Handle Problem Language Result Execution time Memory
251819 2020-07-22T10:38:20 Z VEGAnn Topovi (COCI15_topovi) C++14
0 / 120
 1941 ms 63008 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, crow, ccol;
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;

        crow[r]++;
        ccol[r]++;
    }

    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;
        crow[r1]--;

        if (crow[r1] == 0){
            crow.erase(r1);
            row.erase(r1);
        }

        col[c1] ^= vl;
        ccol[c1]--;

        if (ccol[c1] == 0){
            ccol.erase(c1);
            col.erase(c1);
        }

        row[r2] ^= vl;
        crow[r2]++;

        col[c2] ^= vl;
        ccol[c2]++;

        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 178 ms 10616 KB Output isn't correct
7 Incorrect 133 ms 8312 KB Output isn't correct
8 Incorrect 102 ms 6904 KB Output isn't correct
9 Incorrect 111 ms 7032 KB Output isn't correct
10 Incorrect 128 ms 7928 KB Output isn't correct
11 Incorrect 1901 ms 62832 KB Output isn't correct
12 Incorrect 1830 ms 62860 KB Output isn't correct
13 Incorrect 1845 ms 62728 KB Output isn't correct
14 Incorrect 1941 ms 62840 KB Output isn't correct
15 Incorrect 1896 ms 62840 KB Output isn't correct
16 Incorrect 1678 ms 62788 KB Output isn't correct
17 Incorrect 1898 ms 62768 KB Output isn't correct
18 Incorrect 1787 ms 62840 KB Output isn't correct
19 Incorrect 1791 ms 63008 KB Output isn't correct
20 Incorrect 1661 ms 62712 KB Output isn't correct