oj.uz

Submission #961693

# Submission time Handle Problem Language Result Execution time Memory
961693 2024-04-12T10:30:19 Z tudor_costin Topovi (COCI15_topovi) C++11
120 / 120
 696 ms 32716 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct hash_pair
{
    template<class t1,class t2>
    int operator()(const pair<t1,t2> p) const
    {
        int h1=hash<t1>{}(p.first);
        int h2=hash<t2>{}(p.second);
        if(h1!=h2) return h1^h2;
        return h1;
    }
};
unordered_map<int,int> xor_col,xor_lin;
unordered_map<int,int> cnt_col,cnt_lin;
unordered_map<pair<int,int>,int,hash_pair> rooks;
void update(int l,int c,ll& sol,int n)
{
    sol=sol-n+cnt_col[xor_lin[l]];
    sol=sol-n+cnt_lin[xor_col[c]];
    if(xor_lin[l]^xor_col[c]) sol++;

    cnt_lin[xor_lin[l]]--;
    xor_lin[l]^=rooks[{l,c}];
    cnt_lin[xor_lin[l]]++;

    cnt_col[xor_col[c]]--;
    xor_col[c]^=rooks[{l,c}];
    cnt_col[xor_col[c]]++;

    sol=sol+n-cnt_col[xor_lin[l]];
    sol=sol+n-cnt_lin[xor_col[c]];
    if(xor_lin[l]^xor_col[c]) sol--;
    return;
}
signed main()
{
    int n,k,p;
    cin>>n>>k>>p;
    cnt_col[0]=n;
    cnt_lin[0]=n;
    ll sol=0;
    while(k--)
    {
        int l,c,x;
        cin>>l>>c>>x;
        rooks[{l,c}]=x;
        update(l,c,sol,n);
    }
    while(p--)
    {
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        update(r1,c1,sol,n);
        rooks[{r2,c2}]=rooks[{r1,c1}];
        update(r2,c2,sol,n);
        rooks[{r1,c1}]=0;
        cout<<sol<<'\n';
    }
    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 66 ms 4944 KB Output is correct
7 Correct 50 ms 4456 KB Output is correct
8 Correct 42 ms 3948 KB Output is correct
9 Correct 50 ms 3940 KB Output is correct
10 Correct 49 ms 4196 KB Output is correct
11 Correct 696 ms 32440 KB Output is correct
12 Correct 681 ms 32716 KB Output is correct
13 Correct 596 ms 32344 KB Output is correct
14 Correct 608 ms 32380 KB Output is correct
15 Correct 603 ms 32252 KB Output is correct
16 Correct 607 ms 32364 KB Output is correct
17 Correct 655 ms 32456 KB Output is correct
18 Correct 601 ms 32384 KB Output is correct
19 Correct 652 ms 32296 KB Output is correct
20 Correct 617 ms 32372 KB Output is correct