Submission #574312

#	Time	Username	Problem	Language	Result	Execution time	Memory
574312		kshitij_sodani	Event Hopping (BOI22_events)	C++14	100 / 100	537 ms	37444 KiB

events

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
int aa[100001];
int bb[100001];
int par[100001][20];
int ans[100001];
pair<int,int> tree[100001*8];
vector<pair<int,int>> pre[100001];
void update(int no,int l,int r,int i,pair<int,int> j){
	if(l==r){
		tree[no]=min(tree[no],j);
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,j);
		}
		else{
			update(no*2+2,mid+1,r,i,j);
		}
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
	}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb){
		return {1e9,-1};
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=0;i<8*n;i++){
		tree[i]={1e9,-1};
	}

	vector<pair<int,pair<int,int>>> ss;
	map<int,int> tt;
	map<int,int> tt2;
	for(int i=0;i<n;i++){
		cin>>aa[i]>>bb[i];
		tt[aa[i]]++;
		tt[bb[i]]++;
		/*ss.pb({aa[i],{0,i}});
		ss.pb({bb[i],{1,i}});*/
	}
	int ind=-1;
	for(auto j:tt){
		ind++;
		tt2[j.a]=ind;
	}
	for(int i=0;i<n;i++){
		aa[i]=tt2[aa[i]];
		bb[i]=tt2[bb[i]];
		update(0,0,ind,bb[i],{aa[i],i});
	}
	for(int i=0;i<n;i++){
		pair<int,int> x=query(0,0,ind,aa[i],bb[i]);
		if(x.a<aa[i]){
			par[i][0]=x.b;
		}
		else{
			par[i][0]=-1;
		}
	}
	sort(ss.begin(),ss.end());
	
/*	for(int i=0;i<n;i++){
		cout<<par[i][0]<<",";
	}
	cout<<endl;*/
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	for(int ii=0;ii<q;ii++){
		int l,r;
		cin>>l>>r;
		l--;
		r--;

		if(bb[r]<bb[l]){
			cout<<"impossible"<<endl;
			continue;
		}
		if(l==r){
			cout<<0<<endl;
			continue;
		}
		if(aa[r]<=bb[l] and bb[r]>=bb[l]){
			cout<<1<<endl;
			continue;
		}
		int cur=r;
		int su=0;
		for(int j=19;j>=0;j--){
			if(par[cur][j]>=0){
				if(aa[par[cur][j]]>bb[l]){
					cur=par[cur][j];
					su+=(1<<j);
				}
			}

		}
		if(par[cur][0]==-1){
			su=-1;
		}
		else{
			cur=par[cur][0];
			su+=2;
		}
		if(su==-1){
			cout<<"impossible"<<endl;
			continue;
		}
		cout<<su<<endl;
		
		





	}
	/*for(int ii=0;ii<n;ii++){
		if(pre[ii].size()){
			pair<int,int> ma={-1,-1};
			for(int i=0;i<n;i++){
				par[i][0]=-1;
			}
			for(auto j:ss){
				if(bb[j.b.b]>bb[ii]){
					continue;
				}
				if(j.b.a==0){
					//cur.insert({bb[j.b.b],j.b.b});
					ma=max(ma,{bb[j.b.b],j.b.b});
				}
				else{
					if(ma.a>j.a){

						par[j.b.b][0]=ma.b;
					}
				}
			}
			for(int j=1;j<20;j++){
				for(int i=0;i<n;i++){
					if(par[i][j-1]==-1){
						par[i][j]=-1;
					}
					else{
						par[i][j]=par[par[i][j-1]][j-1];
					}
				}
			}
			for(auto jj:pre[ii]){
				int r=ii;
				int l=jj.a;
				if(l==r){
					ans[jj.b]=0;
					continue;
				}
				if(bb[r]<bb[l]){
					ans[jj.b]=-1;
					continue;
				}
				int su=0;
				int cur=l;
				for(int j=19;j>=0;j--){
					if(par[cur][j]>=0){
						if(bb[par[cur][j]]<bb[r]){
							su+=(1<<j);
							cur=par[cur][j];
						}
					}
				}
				//if(par[cur][0]>=0){
					
					if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
						su++;
						cur=par[cur][0];
					}
					else{
						if(par[cur][0]>=0){
							cur=par[cur][0];
							if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
								su+=2;
							}
							else{
								su=-1;
							}
						}
						else{
							su=-1;
						}
					}
				//}
				//else{
				//	su=-1;
				//}

				ans[jj.b]=su;
			}
		}
	}
	for(int i=0;i<q;i++){
		if(ans[i]==-1){
			cout<<"impossible"<<endl;
		}
		else{
			cout<<ans[i]<<endl;
		}
	}

	



*/


	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30