제출 #1329548

#제출 시각아이디문제언어결과실행 시간메모리
1329548MuhammadSaramTopovi (COCI15_topovi)C++20
6 / 120
1084 ms36264 KiB
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N = 3, M = 1e6 + 1;
const int N1 = 151, M1 = 5001;

int pre[N][M], pre1[N1][M1], cnt;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int n,k,q;
	cin>>n>>k>>q;
	map<int,int> mr, mc, ct, ct1, cnt, cnt1;
	map<pair<int,int>,int> val;
	for (int i=0;i<k;i++)
	{
		int r,c,x;
		cin>>r>>c>>x;
		val[{r,c}]=x;
		ct[r]++, ct1[c]++, mr[r]^=x, mc[c]^=x;
	}
	int sub=0,t=0,t1=0;
	for (auto [x,i]:mr)
		cnt[i]++,t+=(i>0);
	for (auto [x,i]:mc)
		cnt1[i]++, sub+=cnt[i], t1+=(i>0);
	while (q--)
	{
		int r,c,r1,c1;
		cin>>r1>>c1>>r>>c;
		ct[r1]--, ct1[c1]--;
		int x=val[{r1,c1}];
		if (!ct[r1]) ct.erase(r1);
		if (!ct1[c1]) ct1.erase(c1);
		set<int> se;
		se.insert(mr[r1]), se.insert(mc[c1]), se.insert(mr[r1]^x), se.insert(mc[c1]^x);
		se.insert(mr[r]), se.insert(mc[c]), se.insert(mr[r]^x), se.insert(mc[c]^x);
		for (int i:se)
			sub-=cnt[i]*cnt1[i]*(i>0);
		cnt[mr[r1]]--, cnt1[mc[c1]]--;
		if (mr[r1]) t--; if (mc[c1]) t1--; 
		mr[r1]^=x, mc[c1]^=x;
		cnt[mr[r1]]++, cnt1[mc[c1]]++;
		if (mr[r1]) t++; if (mc[c1]) t1++; 
		if (mr[r]) t--; if (mc[c]) t1--; 
		cnt[mr[r]]--, cnt1[mc[c]]--;
		mr[r]^=x, mc[c]^=x;
		cnt[mr[r]]++, cnt1[mc[c]]++;
		if (mr[r]) t++; if (mc[c]) t1++; 
		for (int i:se)
			sub+=cnt[i]*cnt1[i]*(i>0);
		ct[r]++, ct1[c]++;
		cout<<t*t1-sub+t*(n-t1)+t1*(n-t)<<endl;
		val.erase({r1,c1}), val[{r,c}]=x;
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...