oj.uz

Submission #541983

# Submission time Handle Problem Language Result Execution time Memory
541983 2022-03-25T00:22:48 Z Olympia Topovi (COCI15_topovi) C++17
120 / 120
 933 ms 39884 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 (int64_t N) {
        oc1[0] = oc2[0] = N;
        tot = N * N;
    }
};
int main() {
    //freopen("inp.txt", "r", stdin);
    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
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 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 Correct 84 ms 6208 KB Output is correct
7 Correct 64 ms 5544 KB Output is correct
8 Correct 50 ms 4556 KB Output is correct
9 Correct 56 ms 4716 KB Output is correct
10 Correct 59 ms 4840 KB Output is correct
11 Correct 866 ms 39796 KB Output is correct
12 Correct 933 ms 39884 KB Output is correct
13 Correct 858 ms 39772 KB Output is correct
14 Correct 916 ms 39876 KB Output is correct
15 Correct 843 ms 39832 KB Output is correct
16 Correct 883 ms 39764 KB Output is correct
17 Correct 867 ms 39756 KB Output is correct
18 Correct 851 ms 39860 KB Output is correct
19 Correct 899 ms 39764 KB Output is correct
20 Correct 866 ms 39700 KB Output is correct