제출 #1313469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313469		thunopro	Topovi (COCI15_topovi)	C++20	120 / 120	266 ms	26464 KiB

topovi

#include <bits/stdc++.h>
using namespace std;

static inline long long keypos(int r, int c) {
    return ( (long long)r << 32 ) | (unsigned int)c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    int K, P;
    cin >> N >> K >> P;

    unordered_map<int,int> rowxor, colxor;
    unordered_map<int,long long> rowcnt, colcnt;
    unordered_map<long long,int> pos;

    rowxor.reserve(400000);
    colxor.reserve(400000);
    rowcnt.reserve(400000);
    colcnt.reserve(400000);
    pos.reserve(250000);

    rowcnt[0] = N;
    colcnt[0] = N;

    long long total = N * N;
    long long safe = total;

    auto getCnt = [&](unordered_map<int,long long> &mp, int v) -> long long {
        auto it = mp.find(v);
        if (it == mp.end()) return 0;
        return it->second;
    };

    auto incCnt = [&](unordered_map<int,long long> &mp, int v) {
        mp[v] = getCnt(mp, v) + 1;
    };

    auto decCnt = [&](unordered_map<int,long long> &mp, int v) {
        auto it = mp.find(v);
        if (it == mp.end()) return;
        it->second--;
        if (it->second == 0) mp.erase(it);
    };

    auto getXor = [&](unordered_map<int,int> &mp, int id) -> int {
        auto it = mp.find(id);
        if (it == mp.end()) return 0;
        return it->second;
    };

    auto setXor = [&](unordered_map<int,int> &mp, int id, int val) {
        if (val == 0) mp.erase(id);
        else mp[id] = val;
    };

    auto updRow = [&](int r, int x) {
        int oldv = getXor(rowxor, r);
        int newv = oldv ^ x;
        safe -= getCnt(colcnt, oldv);
        decCnt(rowcnt, oldv);
        safe += getCnt(colcnt, newv);
        incCnt(rowcnt, newv);
        setXor(rowxor, r, newv);
    };

    auto updCol = [&](int c, int x) {
        int oldv = getXor(colxor, c);
        int newv = oldv ^ x;
        safe -= getCnt(rowcnt, oldv);
        decCnt(colcnt, oldv);
        safe += getCnt(rowcnt, newv);
        incCnt(colcnt, newv);
        setXor(colxor, c, newv);
    };

    for (int i = 0; i < K; i++) {
        int r, c, x;
        cin >> r >> c >> x;
        pos[keypos(r, c)] = x;
        updRow(r, x);
        updCol(c, x);
    }

    for (int i = 0; i < P; i++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;

        long long k1 = keypos(r1, c1);
        int x = pos[k1];
        pos.erase(k1);

        updRow(r1, x);
        updCol(c1, x);
        updRow(r2, x);
        updCol(c2, x);

        pos[keypos(r2, c2)] = x;

        cout << (total - safe) << "\n";
    }

    return 0;
}

• Subtask 1: 120 / 120