Submission #695045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695045	2023-02-04T17:04:36 Z	Nhoksocqt1	Topovi (COCI15_topovi)	C++17	120 / 120	547 ms	38352 KB

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

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.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	35 ms	5652 KB	Output is correct
7	Correct	37 ms	5088 KB	Output is correct
8	Correct	34 ms	4388 KB	Output is correct
9	Correct	51 ms	4392 KB	Output is correct
10	Correct	30 ms	4548 KB	Output is correct
11	Correct	455 ms	38296 KB	Output is correct
12	Correct	434 ms	38304 KB	Output is correct
13	Correct	489 ms	38236 KB	Output is correct
14	Correct	455 ms	38216 KB	Output is correct
15	Correct	547 ms	38216 KB	Output is correct
16	Correct	545 ms	38352 KB	Output is correct
17	Correct	480 ms	38244 KB	Output is correct
18	Correct	477 ms	38280 KB	Output is correct
19	Correct	542 ms	38296 KB	Output is correct
20	Correct	498 ms	38228 KB	Output is correct