Submission #448732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448732	2021-08-01T08:32:57 Z	IvnF	Topovi (COCI15_topovi)	C++14	120 / 120	1225 ms	45880 KB

topovi

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ull unsigned long long
#define fi first
#define se second
#define ld long double
ll n, k, p, ans;
map<pair<ll, ll>, ll>arr;
map<ll, ll>xorbaris, xorkolom, cntbaris, cntkolom; 

void upd(ll r, ll c, ll val){
	ans-=n-cntkolom[xorbaris[r]]; 
	ans-=n-cntbaris[xorkolom[c]];

	cntbaris[xorbaris[r]]--;
	xorbaris[r]^=val;
	cntbaris[xorbaris[r]]++;
	cntkolom[xorkolom[c]]--;
	xorkolom[c]^=val;
	cntkolom[xorkolom[c]]++;

	ans+=n-cntkolom[xorbaris[r]];
	ans+=n-cntbaris[xorkolom[c]];

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> p;
	cntbaris[0]=cntkolom[0]=n;
	for(int i=1;i<=k;++i){
		ll r, c, x; cin >> r >> c >> x;
		upd(r, c, x);
	}
	for(int q=0;q<p;++q){
		ll r1, r2, c1, c2; cin >> r1 >> c1 >> r2 >> c2;
		ll x=arr[{r1, c1}];
		upd(r1, c1, x);
		upd(r2, c2, x);
		cout << ans << '\n';
	}
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	113 ms	6932 KB	Output is correct
7	Correct	93 ms	6204 KB	Output is correct
8	Correct	84 ms	5060 KB	Output is correct
9	Correct	79 ms	5328 KB	Output is correct
10	Correct	85 ms	5376 KB	Output is correct
11	Correct	1074 ms	45640 KB	Output is correct
12	Correct	1225 ms	45760 KB	Output is correct
13	Correct	1108 ms	45860 KB	Output is correct
14	Correct	1068 ms	45764 KB	Output is correct
15	Correct	1160 ms	45772 KB	Output is correct
16	Correct	1108 ms	45800 KB	Output is correct
17	Correct	1108 ms	45880 KB	Output is correct
18	Correct	1071 ms	45764 KB	Output is correct
19	Correct	1063 ms	45748 KB	Output is correct
20	Correct	1071 ms	45836 KB	Output is correct