oj.uz

Submission #217816

# Submission time Handle Problem Language Result Execution time Memory
217816 2020-03-30T20:05:54 Z TadijaSebez Sweeping (JOI20_sweeping) C++11
11 / 100
 18000 ms 209680 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12672 KB Output is correct
2 Correct 22 ms 12672 KB Output is correct
3 Correct 14 ms 12416 KB Output is correct
4 Correct 22 ms 12788 KB Output is correct
5 Correct 30 ms 12928 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5001 ms 134272 KB Output is correct
2 Correct 4841 ms 140688 KB Output is correct
3 Correct 4906 ms 143036 KB Output is correct
4 Correct 5029 ms 187604 KB Output is correct
5 Correct 6292 ms 197992 KB Output is correct
6 Correct 5227 ms 153100 KB Output is correct
7 Correct 4903 ms 144484 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2946 ms 179044 KB Output is correct
2 Correct 2731 ms 164964 KB Output is correct
3 Correct 2817 ms 191708 KB Output is correct
4 Execution timed out 18053 ms 209680 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2946 ms 179044 KB Output is correct
2 Correct 2731 ms 164964 KB Output is correct
3 Correct 2817 ms 191708 KB Output is correct
4 Execution timed out 18053 ms 209680 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12672 KB Output is correct
2 Correct 22 ms 12672 KB Output is correct
3 Correct 14 ms 12416 KB Output is correct
4 Correct 22 ms 12788 KB Output is correct
5 Correct 30 ms 12928 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 5001 ms 134272 KB Output is correct
8 Correct 4841 ms 140688 KB Output is correct
9 Correct 4906 ms 143036 KB Output is correct
10 Correct 5029 ms 187604 KB Output is correct
11 Correct 6292 ms 197992 KB Output is correct
12 Correct 5227 ms 153100 KB Output is correct
13 Correct 4903 ms 144484 KB Output is correct
14 Correct 2946 ms 179044 KB Output is correct
15 Correct 2731 ms 164964 KB Output is correct
16 Correct 2817 ms 191708 KB Output is correct
17 Execution timed out 18053 ms 209680 KB Time limit exceeded
18 Halted 0 ms 0 KB -