Submission #695045

#	Time	Username	Problem	Language	Result	Execution time	Memory
695045		Nhoksocqt1	Topovi (COCI15_topovi)	C++17	120 / 120	547 ms	38352 KiB

topovi

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define N 100005
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
    bool minus = false;
    int result = 0;
    char ch;
    ch = getchar();
    while(true) {
        if(ch == '-') break;
        if(ch >= '0' && ch <= '9') break;
        ch = getchar();
    }

    if(ch == '-') minus = true; else result = ch - '0';
    while(true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result * 10 + (ch - '0');
    }

    if(minus)
        return -result;
    else
        return result;
}

struct HashPair {
    ll operator() (const ii &a) const {
        return 1LL * a.fi + a.se;
    }
};

unordered_map<ii, int, HashPair> Map;
unordered_map<int, int> rowXor, colXor, cntRow, cntCol;

ll result;
int nRow, numRook, numDiffx, numDiffy, numQuery;

inline int getMap(const unordered_map<int, int> &Map, int key) {
    auto it = Map.find(key);
    return (it == Map.end()) ? 0 : it->se;
}

void revRook(unordered_map<int, int> &rowXor, unordered_map<int, int> &cntRow, const unordered_map<int, int> &cntCol, int x, int w) {
    int &rowx(rowXor[x]);
    result += -getMap(cntCol, rowx) + getMap(cntCol, rowx ^ w);
    --cntRow[rowx], ++cntRow[rowx ^ w];

    rowx ^= w;
}

void process() {
    cin >> nRow >> numRook >> numQuery;
    cntRow[0] = cntCol[0] = nRow;

    result = 1LL * nRow * nRow;
    for (int i = 1; i <= numRook; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        Map[ii(x, y)] = w;
        revRook(rowXor, cntRow, cntCol, x, w);
        revRook(colXor, cntCol, cntRow, y, w);
    }

    for (int t = 0; t < numQuery; ++t) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        int &w = Map[ii(x, y)];

        if(x != u)
            revRook(rowXor, cntRow, cntCol, x, w), revRook(rowXor, cntRow, cntCol, u, w);

        if(y != v)
            revRook(colXor, cntCol, cntRow, y, w), revRook(colXor, cntCol, cntRow, v, w);

        Map[ii(u, v)] = w;

        cout << 1LL * nRow * nRow - result << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("topovi.inp", "r", stdin);
//    freopen("topovi.out", "w", stdout);

    process();
    return 0;
}

Compilation message (stderr)

topovi.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
topovi.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 120 / 120