oj.uz

Submission #541980

# Submission time Handle Problem Language Result Execution time Memory
541980 2022-03-25T00:14:28 Z Olympia Topovi (COCI15_topovi) C++17
6 / 120
 2000 ms 50076 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;
    }
};
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 < N; 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';
    }
}

Subtask #1
6.0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Correct 1 ms 316 KB Output is correct
3 Incorrect 1 ms 316 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 854 ms 9280 KB Output isn't correct
7 Incorrect 489 ms 7492 KB Output isn't correct
8 Incorrect 734 ms 6180 KB Output isn't correct
9 Incorrect 728 ms 6256 KB Output isn't correct
10 Incorrect 722 ms 6996 KB Output isn't correct
11 Execution timed out 2078 ms 50076 KB Time limit exceeded
12 Execution timed out 2065 ms 50044 KB Time limit exceeded
13 Execution timed out 2082 ms 49888 KB Time limit exceeded
14 Execution timed out 2060 ms 50020 KB Time limit exceeded
15 Execution timed out 2070 ms 49920 KB Time limit exceeded
16 Execution timed out 2049 ms 49912 KB Time limit exceeded
17 Execution timed out 2069 ms 50000 KB Time limit exceeded
18 Execution timed out 2048 ms 49996 KB Time limit exceeded
19 Execution timed out 2057 ms 49996 KB Time limit exceeded
20 Execution timed out 2073 ms 49904 KB Time limit exceeded