Submission #217816

#	Time	Username	Problem	Language	Result	Execution time	Memory
217816		TadijaSebez	Sweeping (JOI20_sweeping)	C++11	11 / 100	18053 ms	209680 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
//Bottom-up Treap
const int N=1500050;
int ls[N],rs[N],tsz,fa[N],x[N],y[N],lzx[N],lzy[N],sz[N],pri[N];
void upd_x(int c,int f){if(c)x[c]=f,lzx[c]=f;}
void upd_y(int c,int f){if(c)y[c]=f,lzy[c]=f;}
void push(int c){
	if(~lzx[c])upd_x(ls[c],lzx[c]),upd_x(rs[c],lzx[c]),lzx[c]=-1;
	if(~lzy[c])upd_y(ls[c],lzy[c]),upd_y(rs[c],lzy[c]),lzy[c]=-1;
}
void pull(int c){if(c)sz[c]=sz[ls[c]]+1+sz[rs[c]];}
int cmp(int a,int b){return mp(x[a],y[a])<mp(x[b],y[b]);}
int Merge(int a,int b){
	if(!b || !a)return a^b;
	if(pri[a]>pri[b]){
		push(a);
		int c=Merge(rs[a],b);
		rs[a]=c;
		if(c)fa[c]=a;
		pull(a);
		return a;
	}else{
		push(b);
		int c=Merge(a,ls[b]);
		ls[b]=c;
		if(c)fa[c]=b;
		pull(b);
		return b;
	}
}
void Split(int c,int &l,int lp,int &r,int rp,int X,int Y){
	if(!c){l=r=0;return;}
	push(c);
	if(x[c]<=X && y[c]<=Y){
		l=c;
		Split(rs[c],rs[l],l,r,rp,X,Y);
		fa[c]=lp;
	}else{
		r=c;
		Split(ls[c],l,lp,ls[r],r,X,Y);
		fa[c]=rp;
	}
	pull(c);
}
pair<int,int> Split(int c,int X,int Y){
	int l=0,r=0;
	Split(c,l,0,r,0,X,Y);
	return {l,r};
}
int Insert(int c,int nd){
	int l=0,r=0;
	Split(c,l,0,r,0,x[nd],y[nd]);
	return Merge(l,Merge(nd,r));
}
vector<int> nds;
void Dstr(int c){
	if(!c)return;
	push(c);
	Dstr(ls[c]);
	Dstr(rs[c]);
	ls[c]=rs[c]=fa[c]=0;
	sz[c]=1;
	nds.pb(c);
}
int InsAll(int c,int d){
	nds.clear();
	Dstr(c);
	for(int i:nds)d=Insert(d,i);
	return d;
}
void dwn(int nd){if(fa[nd])dwn(fa[nd]);push(nd);}
void Print(int nd){
	dwn(nd);
	printf("%i %i\n",x[nd],y[nd]);
}
struct ST{
	vector<vector<int>> work;
	int sz;
	ST(){}
	void init(int n){sz=n;work.resize(sz*2);}
	void Add(int c,int l,int r){
		//printf("put %i %i %i\n",l,r,c);
		for(l+=sz,r+=sz;l<=r;l>>=1,r>>=1){
			if(l%2==1)work[l++].pb(c);
			if(r%2==0)work[r--].pb(c);
		}
	}
	vector<int> Get(int x){
		//printf("take %i\n");
		vector<int> ans;
		for(x+=sz;x;x>>=1){
			for(int c:work[x])ans.pb(c);
			work[x].clear();
		}
		return ans;
	}
}HST,VST;
struct CPS{
	vector<int> all;
	CPS(){}
	void Add(int x){all.pb(x);}
	void Build(){sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());}
	int GetL(int x){return lower_bound(all.begin(),all.end(),x)-all.begin();}
	int GetR(int x){return upper_bound(all.begin(),all.end(),x)-all.begin()-1;}
}HCP,VCP;
int n;
pair<int,int> FH(int X,int Y){
	return {HCP.GetL(X),HCP.GetR(n-Y)};
}
pair<int,int> FV(int X,int Y){
	return {VCP.GetL(Y),VCP.GetR(n-X)};
}
void Add(int c){
	if(!c)return;
	int tmp=c;
	while(ls[c])push(c),c=ls[c];
	pair<int,int> h=FH(x[c],y[c]);
	pair<int,int> v=FV(x[c],y[c]);
	HST.Add(tmp,h.first,h.second);
	VST.Add(tmp,v.first,v.second);
}
mt19937 rng(time(0));
void NewPt(int X,int Y){
	++tsz;
	x[tsz]=X;y[tsz]=Y;
	sz[tsz]=1;
	pri[tsz]=rng();
	Add(tsz);
}
void cut(vector<int> &all){
	vector<int> tmp;
	for(int c:all)if(!fa[c] && c)tmp.pb(c);
	all=tmp;
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
}
void H_sweep(int X){
	vector<int> all=HST.Get(HCP.GetL(X));
	cut(all);
	//printf("H %i\n",X);
	for(int &c:all){
		//printf("(%i %i)",x[c],y[c]);
		int l,r;tie(l,r)=Split(c,X,n-X);
		if(l!=0)Add(r);
		if(l!=0)upd_y(l,n-X);
		c=l;
	}
	//printf("\n");
	while(all.size()>1){
		int a=all.back();
		all.pop_back();
		int b=all.back();
		all.pop_back();
		if(sz[a]>sz[b])swap(a,b);
		all.pb(InsAll(a,b));
	}
	if(all.size()==1 && all[0]!=0)
		Add(all[0]);
}
void V_sweep(int Y){
	vector<int> all=VST.Get(VCP.GetL(Y));
	cut(all);
	//printf("V %i\n",Y);
	for(int &c:all){
		//printf("(%i %i)",x[c],y[c]);
		int l,r;tie(l,r)=Split(c,n-Y,Y);
		Add(r);
		if(l!=0)upd_x(l,n-Y);
		c=l;
	}
	//printf("\n");
	while(all.size()>1){
		int a=all.back();
		all.pop_back();
		int b=all.back();
		all.pop_back();
		if(sz[a]>sz[b])swap(a,b);
		all.pb(InsAll(a,b));
	}
	if(all.size()==1 && all[0]!=0)
		Add(all[0]);
}
int t[N],xx[N],yy[N],l[N];
int main(){
	for(int i=0;i<N;i++)lzx[i]=lzy[i]=-1;
	int m,q;
	scanf("%i %i %i",&n,&m,&q);
	for(int i=1;i<=m;i++)t[i]=4,scanf("%i %i",&xx[i],&yy[i]);
	for(int i=m+1;i<=m+q;i++){
		scanf("%i",&t[i]);
		if(t[i]<4)scanf("%i",&l[i]);
		else scanf("%i %i",&xx[i],&yy[i]);
		if(t[i]==2)VCP.Add(l[i]);
		if(t[i]==3)HCP.Add(l[i]);
	}
	VCP.Build();HCP.Build();
	VST.init(VCP.all.size());
	HST.init(HCP.all.size());
	q+=m;
	for(int i=1;i<=q;i++){
		if(t[i]==1)Print(l[i]);
		else if(t[i]==2)V_sweep(l[i]);
		else if(t[i]==3)H_sweep(l[i]);
		else NewPt(xx[i],yy[i]);
	}
	return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:191:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++)t[i]=4,scanf("%i %i",&xx[i],&yy[i]);
                       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&t[i]);
   ~~~~~^~~~~~~~~~~~
sweeping.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(t[i]<4)scanf("%i",&l[i]);
             ~~~~~^~~~~~~~~~~~
sweeping.cpp:195:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%i %i",&xx[i],&yy[i]);
        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25