Submission #290136

#	Time	Username	Problem	Language	Result	Execution time	Memory
290136		TadijaSebez	Sweeping (JOI20_sweeping)	C++11	100 / 100	4788 ms	603636 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
struct Query{
	int type;
	int idx,x,y;
	int l;
	Query(){}
	Query(int t,int i,int X,int Y):type(t),idx(i),x(X),y(Y),l(-1){}
	Query(int t,int i,int L):type(t),idx(i),l(L),x(-1),y(-1){}
};
const int N=1500050;
const int M=2*N;
pii ans[N];
int n,m,q;
int val[M],myc[N*2],tsz,rem[N];
vector<int> cmp[M];
int add(int i,int v){tsz++;val[tsz]=v;myc[i]=tsz;cmp[tsz]={i};return tsz;}
int mrg(int a,int b){
	if(cmp[a].size()>cmp[b].size())swap(a,b);
	for(int i:cmp[a]){
		myc[i]=b;
		cmp[b].pb(i);
	}
	cmp[a].clear();
	return b;
}
void DNC(int l,int r,vector<Query> Qs){
	if(Qs.empty())return;
	int mid=l+r>>1;
	int X=mid,Y=n-mid;
	priority_queue<pii> xs,ys;
	vector<Query> LQ,RQ;
	for(Query qu:Qs){
		if(qu.type==1){
			int x=val[myc[qu.idx<<1]],y=val[myc[qu.idx<<1|1]];
			if(rem[qu.idx]==1)RQ.pb(qu);
			else if(rem[qu.idx]==2)LQ.pb(qu);
			else ans[qu.l]={x,y};
		}else if(qu.type==2){
			if(qu.l<Y){
				RQ.pb(qu);
				while(ys.size()&&-ys.top().first<=qu.l){
					int c=ys.top().second;
					ys.pop();
					for(int i:cmp[c])if(!rem[i/2]){
						int x=n-qu.l,y=val[c];
						RQ.pb(Query(4,i/2,x,y));
						rem[i/2]=1;
					}
				}
			}else{
				int now=0;
				while(xs.size()&&-xs.top().first<n-qu.l){
					int tmp=xs.top().second;
					xs.pop();
					now=now?mrg(now,tmp):tmp;
				}
				if(now)val[now]=n-qu.l,xs.push({-val[now],now});
				LQ.pb(qu);
			}
		}else if(qu.type==3){
			if(qu.l<X){
				LQ.pb(qu);
				while(xs.size()&&-xs.top().first<=qu.l){
					int c=xs.top().second;
					xs.pop();
					for(int i:cmp[c])if(!rem[i/2]){
						int x=val[c],y=n-qu.l;
						LQ.pb(Query(4,i/2,x,y));
						rem[i/2]=2;
					}
				}
			}else{
				int now=0;
				while(ys.size()&&-ys.top().first<n-qu.l){
					int tmp=ys.top().second;
					ys.pop();
					now=now?mrg(now,tmp):tmp;
				}
				if(now)val[now]=n-qu.l,ys.push({-val[now],now});
				RQ.pb(qu);
			}
		}else{
			if(qu.x>X)rem[qu.idx]=1,RQ.pb(qu);
			else if(qu.y>Y)rem[qu.idx]=2,LQ.pb(qu);
			else{
				rem[qu.idx]=0;
				xs.push({-qu.x,add(qu.idx<<1,qu.x)});
				ys.push({-qu.y,add(qu.idx<<1|1,qu.y)});
			}
		}
	}
	tsz=0;
	if(l==r)return;
	if(l+1==r)DNC(r,r,RQ);
	else{
		DNC(l,mid,LQ);
		DNC(mid,r,RQ);
	}
}
int main(){
	scanf("%i %i %i",&n,&m,&q);
	vector<Query> Qs;
	for(int i=1,x,y;i<=m;i++){
		scanf("%i %i",&x,&y);
		Qs.pb(Query(4,i,x,y));
	}
	int z=0;
	for(int i=1;i<=q;i++){
		int t;scanf("%i",&t);
		if(t==1){
			int idx;scanf("%i",&idx);
			Qs.pb(Query(1,idx,++z));
		}else if(t==2||t==3){
			int l;scanf("%i",&l);
			Qs.pb(Query(t,-1,l));
		}else{
			int x,y;scanf("%i %i",&x,&y);
			Qs.pb(Query(4,++m,x,y));
		}
	}
	DNC(0,n,Qs);
	for(int i=1;i<=z;i++)printf("%i %i\n",ans[i].first,ans[i].second);
	return 0;
}

Compilation message (stderr)

sweeping.cpp: In constructor 'Query::Query(int, int, int)':
sweeping.cpp:8:6: warning: 'Query::l' will be initialized after [-Wreorder]
    8 |  int l;
      |      ^
sweeping.cpp:7:10: warning:   'int Query::x' [-Wreorder]
    7 |  int idx,x,y;
      |          ^
sweeping.cpp:11:2: warning:   when initialized here [-Wreorder]
   11 |  Query(int t,int i,int L):type(t),idx(i),l(L),x(-1),y(-1){}
      |  ^~~~~
sweeping.cpp: In function 'void DNC(int, int, std::vector<Query>)':
sweeping.cpp:31:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int mid=l+r>>1;
      |          ~^~
sweeping.cpp: In function 'int main()':
sweeping.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |  scanf("%i %i %i",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%i %i",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   int t;scanf("%i",&t);
      |         ~~~~~^~~~~~~~~
sweeping.cpp:114:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |    int idx;scanf("%i",&idx);
      |            ~~~~~^~~~~~~~~~~
sweeping.cpp:117:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |    int l;scanf("%i",&l);
      |          ~~~~~^~~~~~~~~
sweeping.cpp:120:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |    int x,y;scanf("%i %i",&x,&y);
      |            ~~~~~^~~~~~~~~~~~~~~

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