oj.uz

Submission #541982

# Submission time Handle Problem Language Result Execution time Memory
541982 2022-03-25T00:20:10 Z Olympia Topovi (COCI15_topovi) C++17
30 / 120
 978 ms 40200 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>
#include <queue>

using namespace std;
class DynamicThing {
    map<int64_t,int64_t> oc1;
    map<int64_t,int64_t> oc2;
public:
    int64_t tot = 0;
    void remove (int64_t type, int64_t index) {
        if (type == 1) {
            tot -= oc1[index] * oc2[index];
            oc1[index]--;
            tot += oc1[index] * oc2[index];
        } else {
            tot -= oc1[index] * oc2[index];
            oc2[index]--;
            tot += oc1[index] * oc2[index];
        }
    }
    void add (int64_t type, int64_t index) {
        if (type == 1) {
            tot -= oc1[index] * oc2[index];
            oc1[index]++;
            tot += oc1[index] * oc2[index];
        } else {
            tot -= oc1[index] * oc2[index];
            oc2[index]++;
            tot += oc1[index] * oc2[index];
        }
    }
    DynamicThing (int N) {
        oc1[0] = oc2[0] = N;
        tot = N * N;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    map<int64_t,int64_t> row_xor;
    map<int64_t,int64_t> col_xor;
    int64_t N, K, P;
    cin >> N >> K >> P;
    DynamicThing dt(N);
    map<pair<int64_t,int64_t>,int64_t> loc;
    for (int i = 0; i < K; i++) {
        int64_t r, c, x;
        cin >> r >> c >> x;
        dt.remove(1, row_xor[r]);
        dt.remove(2, col_xor[c]);
        dt.add(1, (row_xor[r] ^= x));
        dt.add(2, (col_xor[c] ^= x));
        loc[{r, c}] = x;
    }
    while (P--) {
        int64_t r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        if (r1 != r2) {
            dt.remove(1, row_xor[r1]);
            dt.remove(1, row_xor[r2]);
            dt.add(1, row_xor[r1] ^= loc[{r1, c1}]);
            dt.add(1, row_xor[r2] ^= loc[{r1, c1}]);
        }
        if (c1 != c2) {
            dt.remove(2, col_xor[c1]);
            dt.remove(2, col_xor[c2]);
            dt.add(2, col_xor[c1] ^= loc[{r1, c1}]);
            dt.add(2, col_xor[c2] ^= loc[{r1, c1}]);
        }
        loc[{r2, c2}] = loc[{r1, c1}];
        loc[{r1, c1}] = 0;
        cout << N * N - dt.tot << '\n';
    }
}

Subtask #1
30.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 118 ms 6204 KB Output isn't correct
7 Incorrect 65 ms 5624 KB Output isn't correct
8 Incorrect 50 ms 4684 KB Output isn't correct
9 Incorrect 53 ms 4708 KB Output isn't correct
10 Incorrect 61 ms 4880 KB Output isn't correct
11 Incorrect 898 ms 40200 KB Output isn't correct
12 Incorrect 927 ms 40132 KB Output isn't correct
13 Incorrect 910 ms 40140 KB Output isn't correct
14 Incorrect 881 ms 40136 KB Output isn't correct
15 Incorrect 903 ms 40140 KB Output isn't correct
16 Incorrect 918 ms 40140 KB Output isn't correct
17 Incorrect 901 ms 40180 KB Output isn't correct
18 Incorrect 914 ms 40076 KB Output isn't correct
19 Incorrect 978 ms 40096 KB Output isn't correct
20 Incorrect 870 ms 40148 KB Output isn't correct