oj.uz

Submission #251808

# Submission time Handle Problem Language Result Execution time Memory
251808 2020-07-22T10:29:05 Z VEGAnn Topovi (COCI15_topovi) C++14
0 / 120
 1560 ms 65540 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]++;
    }

    ans = ll(sz(row)) * ll(sz(col));

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

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

    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]++;

        was.clear();

        cans += del(sR1);
        cans += del(sR2);
        cans += del(sC1);
        cans += del(sC2);

        cout << ll(sz(row)) * ll(sz(col)) - 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 187 ms 12536 KB Output isn't correct
7 Incorrect 128 ms 10744 KB Output isn't correct
8 Incorrect 109 ms 8936 KB Output isn't correct
9 Incorrect 112 ms 9080 KB Output isn't correct
10 Incorrect 132 ms 9592 KB Output isn't correct
11 Runtime error 1360 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 1343 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1420 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1337 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1536 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 1444 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 1536 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 1560 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 1467 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 1423 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)