oj.uz

Submission #541981

# Submission time Handle Problem Language Result Execution time Memory
541981 2022-03-25T00:19:04 Z Olympia Topovi (COCI15_topovi) C++17
30 / 120
 807 ms 34052 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;
const int MOD = 10007;
class DynamicThing {
    map<int,int64_t> oc1;
    map<int,int64_t> oc2;
public:
    int64_t tot = 0;
    void remove (int type, int 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 (int type, int 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;
    }
    void print () {
        int ans = 0;
        for (auto& p: oc1) {
            ans += p.second * oc2[p.first];
        }
        cout << ans;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    map<int,int> row_xor;
    map<int,int> col_xor;
    int64_t N, K, P;
    cin >> N >> K >> P;
    DynamicThing dt(N);
    map<pair<int,int>,int> 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;
    }
    //cout << dt.tot << '\n';
    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';
        //dt.print();
        //return 0;
    }
}

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 82 ms 5328 KB Output isn't correct
7 Incorrect 65 ms 4716 KB Output isn't correct
8 Incorrect 50 ms 3868 KB Output isn't correct
9 Incorrect 53 ms 4236 KB Output isn't correct
10 Incorrect 62 ms 4176 KB Output isn't correct
11 Incorrect 784 ms 33932 KB Output isn't correct
12 Incorrect 802 ms 33996 KB Output isn't correct
13 Incorrect 790 ms 33956 KB Output isn't correct
14 Incorrect 793 ms 33856 KB Output isn't correct
15 Incorrect 799 ms 33956 KB Output isn't correct
16 Incorrect 807 ms 33868 KB Output isn't correct
17 Incorrect 768 ms 33868 KB Output isn't correct
18 Incorrect 787 ms 33976 KB Output isn't correct
19 Incorrect 778 ms 34052 KB Output isn't correct
20 Incorrect 783 ms 33856 KB Output isn't correct