oj.uz

Submission #888130

# Submission time Handle Problem Language Result Execution time Memory
888130 2023-12-16T07:24:48 Z Danet Topovi (COCI15_topovi) C++14
120 / 120
 834 ms 40272 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
 
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
const int OO = 1e9+7;
const int MOD = 1e9+7;
const int N = 1e5+7;
 
map<int,int> xorr,xorc;
map<int,int> cntr,cntc;
map<pair<int,int>,int> rook;
ll ans = 0;
int n,k,p;
void add(int r,int c,int x)
{
    rook[{r,c}] ^= x;
    ans -= n-cntc[xorr[r]];
    ans -= n-cntr[xorc[c]];
    if (xorr[r] != xorc[c]) ans++;
    cntc[xorc[c]]--;
    cntr[xorr[r]]--;
    xorr[r] ^= x;
    xorc[c] ^= x;
    cntc[xorc[c]]++;
    cntr[xorr[r]]++;
    ans += n-cntc[xorr[r]];
    ans += n-cntr[xorc[c]];
    if (xorr[r] != xorc[c]) ans--;
    //db2(xorr[r],xorc[c]);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k >> p;
    cntr[0] = n;
    cntc[0] = n;
    rep(i,k)
    {
    	int r,c,x;
    	cin >> r >> c >> x;
    	add(r,c,x);
        //db1(ans);
    }
    
    
    
    while(p--)
    {
    	int r1,c1,r2,c2;
    	cin >> r1 >> c1 >> r2 >> c2;
        int x = rook[{r1,c1}];
    	add(r1,c1,x);
        add(r2,c2,x);
    	cout << ans << '\n';
    }
    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 89 ms 6096 KB Output is correct
7 Correct 70 ms 5456 KB Output is correct
8 Correct 55 ms 4496 KB Output is correct
9 Correct 61 ms 4588 KB Output is correct
10 Correct 64 ms 4692 KB Output is correct
11 Correct 834 ms 39444 KB Output is correct
12 Correct 818 ms 39508 KB Output is correct
13 Correct 829 ms 39752 KB Output is correct
14 Correct 804 ms 39764 KB Output is correct
15 Correct 802 ms 39532 KB Output is correct
16 Correct 800 ms 39764 KB Output is correct
17 Correct 813 ms 39508 KB Output is correct
18 Correct 806 ms 39576 KB Output is correct
19 Correct 813 ms 39504 KB Output is correct
20 Correct 796 ms 40272 KB Output is correct