oj.uz

Submission #151342

# Submission time Handle Problem Language Result Execution time Memory
151342 2019-09-02T13:49:22 Z path Topovi (COCI15_topovi) C++14
120 / 120
 1738 ms 46048 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define mp make_pair
typedef long long int ll;
map<int,ll> r,c,rc,cc;
map< pair<int,int>, ll> vis;
int n,p,k,a,b;
ll ans,x;
void update(){
    ans-= (n-rc[c[b]]);
    ans-= (n-cc[r[a]]);
    if(r[a]==c[b])
        ans++;
    cc[c[b]]--;
    c[b]=(c[b]^x);
    cc[c[b]]++;
    rc[r[a]]--;
    r[a]=(r[a]^x);
    rc[r[a]]++;
    ans+=(n-rc[c[b]]);
    ans+=(n-cc[r[a]]);
    if(r[a]==c[b])
        ans--;
    return;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>k>>p;
    rc[0]=cc[0]=n;
    while(k--){
        cin>>a>>b>>x;
        vis[mp(a,b)]=x;
        update();
    }
    while(p--){
        cin>>a>>b;
        x=vis[mp(a,b)];
        vis[mp(a,b)]=0;
        update();
        cin>>a>>b;
        update();
        vis[mp(a,b)]=x;
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 177 ms 7036 KB Output is correct
7 Correct 153 ms 6296 KB Output is correct
8 Correct 138 ms 5240 KB Output is correct
9 Correct 116 ms 5240 KB Output is correct
10 Correct 131 ms 5488 KB Output is correct
11 Correct 1557 ms 45900 KB Output is correct
12 Correct 1738 ms 45864 KB Output is correct
13 Correct 1677 ms 45744 KB Output is correct
14 Correct 1581 ms 45964 KB Output is correct
15 Correct 1545 ms 46000 KB Output is correct
16 Correct 1531 ms 45840 KB Output is correct
17 Correct 1558 ms 46048 KB Output is correct
18 Correct 1627 ms 45920 KB Output is correct
19 Correct 1675 ms 45836 KB Output is correct
20 Correct 1590 ms 45960 KB Output is correct