Submission #212899

#	Time	Username	Problem	Language	Result	Execution time	Memory
212899		blacktulip	Topovi (COCI15_topovi)	C++17	0 / 120	1618 ms	65540 KiB

topovi

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define int long long
#define se second
#define mp make_pair
#define pb insert
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
 
int n,m,b[li],a[li],k,flag,t,x[li],y[li],z[li];
int cev;
string s;
map<int,int> sat,sut,visit,visit1,vis,vis1;
map<PII,int> mpp;
set<int> v,v1;
 
main(void){
	scanf("%lld %lld %lld",&n,&k,&t);
	for(int i=1;i<=k;i++){
		scanf("%lld %lld %lld",&x[i],&y[i],&z[i]);
		mpp[mp(x[i],y[i])]=i;
		sat[x[i]]^=z[i];
		sut[y[i]]^=z[i];
		if(visit[x[i]]==0)
		v.pb(x[i]);
		visit[x[i]]++;
		if(visit1[y[i]]==0)
		v1.pb(y[i]);
		visit1[y[i]]++;
	}
	for(auto it=v.begin();it!=v.end();it++){
		vis[sat[*it]]++;
		//~ cout<<sat[*it]<<endl;
	}
	for(auto it=v1.begin();it!=v1.end();it++){
		vis1[sut[*it]]++;
	}
	for(auto it=v.begin();it!=v.end();it++){
		if(sat[*it]){
			cev+=n-vis1[sat[*it]];
		}
		else{
			cev+=(int)v1.size()-vis1[0];
		}
	}
	for(auto it=v1.begin();it!=v1.end();it++){
		if(sut[*it]){
			cev+=n-(int)v.size();
		}
	}
	//~ cout<<vis[0]<<endl;
	while(t--){
		int x1,x2,y1,y2;
		scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
		int i=mpp[mp(x1,y1)];
		//~ cout<<i<<endl;
		if(i==0){printf("%lld\n",cev);continue;}
		if(y1!=y2){
			//~ cout<<"()\n";
			cev-=v.size()-vis[sut[y1]];
			
			if(sut[y1]){
				cev-=n-v.size();
			}
			if(visit1[y1])
			vis1[sut[y1]]--;
			sut[y1]^=z[i];
			vis1[sut[y1]]++;
			//~ cout<<v.size()<<" : ; "<<vis[sut[y1]]<<"::"<<sut[y1]<<endl;
			cev+=v.size()-vis[sut[y1]];
			
			if(sut[y1]){
				cev+=n-v.size();
			}
			cev-=v.size()-vis[sut[y2]];
			if(sut[y2]){
				cev-=n-v.size();
			}
			if(visit1[y2])
			vis1[sut[y2]]--;
			sut[y2]^=z[i];
			vis1[sut[y2]]++;
			cev+=v.size()-vis[sut[y2]];
			if(sut[y2]){
				cev+=n-v.size();
			}
			if(visit1[y1]==1){
				auto it=v1.find(y1);
				v1.erase(it);
			}
			visit1[y1]--;
			if(visit1[y2]==0){
				v1.insert(y2);
			}
			visit1[y2]++;
			mpp[mp(x1,y1)]=0;
			mpp[mp(x2,y2)]=i;
			//~ printf("%lld\n",cev);
			//~ continue;
		}
		if(x1!=x2){
			if(sat[x1]){
				cev-=n-vis1[sat[x1]];
			}
			else{
				cev-=(int)v1.size()-vis1[0];
			}
			if(visit[x1])
			vis[sat[x1]]--;
			sat[x1]^=z[i];
			vis[sat[x1]]++;
			if(sat[x1]){
				cev+=n-vis1[sat[x1]];
			}
			else{
				cev+=(int)v1.size()-vis1[0];
			}
			
			if(sat[x2]){
				cev-=n-vis1[sat[x2]];
			}
			else{
				cev-=(int)v1.size()-vis1[0];
			}
			if(visit[x2])
			vis[sat[x2]]--;
			sat[x2]^=z[i];
			vis[sat[x2]]++;
			if(sat[x2]){
				cev+=n-vis1[sat[x2]];
			}
			else{
				cev+=(int)v1.size()-vis1[0];
			}
			if(visit[x1]==1){
				auto it=v.find(x1);
				v.erase(it);
			}
			visit[x1]--;
			if(visit[x2]==0){
				v.insert(x2);
			}
			visit[x2]++;
			mpp[mp(x1,y1)]=0;
			mpp[mp(x2,y2)]=i;
		}
		//~ cout<<vis[2]<<endl;
		//~ cout<<"**\n";
		printf("%lld\n",cev);
	}
	
	return 0;
	
}

Compilation message (stderr)

topovi.cpp:33:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
topovi.cpp: In function 'int main()':
topovi.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&k,&t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x[i],&y[i],&z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 120