oj.uz

Submission #648716

# Submission time Handle Problem Language Result Execution time Memory
648716 2022-10-07T17:39:07 Z Adominator Topovi (COCI15_topovi) C++17
120 / 120
 468 ms 35880 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()

#define rep(i, a, b) for(ll i=(a); i<(b); i++)
#define repd(i, a, b) for(ll i=(a); i>=(b); i--)

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash {
    const uint64_t C=ll(2e18*acos(0))+71;
    const int RANDOM=chrono::high_resolution_clock::now().time_since_epoch().count();
    ll operator()(ll x) const {
        return __builtin_bswap64((x^RANDOM)*C);
    }
};

gp_hash_table<int, int, chash> rcnt, ccnt, col, row;
map<ar<int, 2>, int> val;
int n, k, p;
ll ans;

void move(int r, int c, int x) {
    ans-=n-rcnt[col[c]];
    ans-=n-ccnt[row[r]];
    if(col[c]^row[r]) ans++;

    --rcnt[row[r]];
    row[r]^=x;
    ++rcnt[row[r]];

    --ccnt[col[c]];
    col[c]^=x;
    ++ccnt[col[c]];

    ans+=n-rcnt[col[c]];
    ans+=n-ccnt[row[r]];
    if(col[c]^row[r]) ans--;

    val[{r, c}]^=x;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k >> p;

    ccnt[0]=rcnt[0]=n;

    rep(i, 0, k) {
        int r, c, x;
        cin >> r >> c >> x;

        move(r, c, x);
    }

    rep(i, 0, p) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;

        int tmp=val[{r1, c1}];
        move(r1, c1, tmp);
        move(r2, c2, tmp);

        cout << ans << '\n';
    }
}

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 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 46 ms 4756 KB Output is correct
7 Correct 35 ms 4320 KB Output is correct
8 Correct 25 ms 3900 KB Output is correct
9 Correct 28 ms 3928 KB Output is correct
10 Correct 30 ms 4060 KB Output is correct
11 Correct 383 ms 32900 KB Output is correct
12 Correct 407 ms 32880 KB Output is correct
13 Correct 414 ms 32940 KB Output is correct
14 Correct 468 ms 32952 KB Output is correct
15 Correct 436 ms 33320 KB Output is correct
16 Correct 465 ms 32864 KB Output is correct
17 Correct 437 ms 35880 KB Output is correct
18 Correct 466 ms 32968 KB Output is correct
19 Correct 411 ms 32920 KB Output is correct
20 Correct 382 ms 34392 KB Output is correct