Submission #541972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541972	2022-03-24T22:43:17 Z	Olympia	Topovi (COCI15_topovi)	C++17	6 / 120	2000 ms	49716 KB

topovi

#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, int quantity) {
        if (type == 1) {
            tot -= oc1[index] * oc2[index];
            oc1[index] -= quantity;
            tot += oc1[index] * oc2[index];
        } else {
            tot -= oc1[index] * oc2[index];
            oc2[index] -= quantity;
            tot += oc1[index] * oc2[index];
        }
    }
    void add (int type, int index, int quantity) {
        if (type == 1) {
            tot -= oc1[index] * oc2[index];
            oc1[index] += quantity;
            tot += oc1[index] * oc2[index];
        } else {
            tot -= oc1[index] * oc2[index];
            oc2[index] += quantity;
            tot += oc1[index] * oc2[index];
        }
    }
};
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;
    dt.add(1, 0, N);
    dt.add(2, 0, 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], 1 );
        dt.remove(2, col_xor[c], 1);
        row_xor[r] ^= x;
        col_xor[c] ^= x;
        dt.add(1, row_xor[r], 1 );
        dt.add(2, col_xor[c], 1);
        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], 1);
            dt.remove(1, row_xor[r2], 1);
            row_xor[r1] ^= loc[{r1, c1}];
            row_xor[r2] ^= loc[{r1, c1}];
            dt.add(1, row_xor[r1], 1);
            dt.add(1, row_xor[r2], 1 );
        }
        if (c1 != c2) {
            dt.remove(2, col_xor[c1], 1);
            dt.remove(2, col_xor[c2], 1);
            col_xor[c1] ^= loc[{r1, c1}];
            col_xor[c2] ^= loc[{r1, c1}];
            dt.add(2, col_xor[c1], 1);
            dt.add(2, col_xor[c2], 1);
        }
        loc[{r2, c2}] = loc[{r1, c1}];
        loc[{r1, c1}] = 0;
        cout << N * N - dt.tot << '\n';
    }
    //cout << 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	212 KB	Output is correct
3	Incorrect	1 ms	212 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	930 ms	8896 KB	Output isn't correct
7	Incorrect	579 ms	6932 KB	Output isn't correct
8	Incorrect	811 ms	5796 KB	Output isn't correct
9	Incorrect	791 ms	5872 KB	Output isn't correct
10	Incorrect	860 ms	6704 KB	Output isn't correct
11	Execution timed out	2099 ms	49660 KB	Time limit exceeded
12	Execution timed out	2062 ms	49576 KB	Time limit exceeded
13	Execution timed out	2063 ms	49692 KB	Time limit exceeded
14	Execution timed out	2076 ms	49696 KB	Time limit exceeded
15	Execution timed out	2027 ms	49536 KB	Time limit exceeded
16	Execution timed out	2071 ms	49684 KB	Time limit exceeded
17	Execution timed out	2090 ms	49476 KB	Time limit exceeded
18	Execution timed out	2084 ms	49528 KB	Time limit exceeded
19	Execution timed out	2088 ms	49588 KB	Time limit exceeded
20	Execution timed out	2085 ms	49716 KB	Time limit exceeded