oj.uz

답안 #541972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541972 2022-03-24T22:43:17 Z Olympia Topovi (COCI15_topovi) C++17
6 / 120
 2000 ms 49716 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, 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

# 결과 실행 시간 메모리 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