Submission #1229109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229109		_rain_	Event Hopping (BOI22_events)	C++20	100 / 100	167 ms	17484 KiB

events

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2e5;
const int INF=(int)1e9;
const int MAXLOG=18;
	int par[N+2][MAXLOG+2];
	int s[N+2],e[N+2],l[N+2],r[N+2];
	int n,q,limit_size;
	vector<int>nen;

int Find(int x){
	return upper_bound(nen.begin(),nen.end(),x)-nen.begin();
}

pair<int,int>st[N*4+2];
	void upd(int id,int l,int r,int pos,pair<int,int>val){
		if (l>pos||r<pos) return;
		if (l==r) st[id]=min(st[id],val);
		else {
			int m=(l+r)/2;
			upd(id*2,l,m,pos,val);
			upd(id*2+1,m+1,r,pos,val);
			st[id]=min(st[id*2],st[id*2+1]);
		}
	}
	pair<int,int>Get(int id,int l,int r,int u,int v){
		if (l>v||r<u) return {INF,INF};
		if (u<=l&&r<=v) return st[id];
		int m=(l+r)/2;
		return min(Get(id*2,l,m,u,v),Get(id*2+1,m+1,r,u,v));
	}

void process(int l,int r){
	int ans=2;
	for(int j=MAXLOG;j>=0;--j){
		if (s[par[r][j]]>e[l]){
			ans+=(1<<j);
			r=par[r][j];
		}
	}
	r=par[r][0];
	if (s[r]<=e[l] && e[l]<=e[r]){
		cout<<ans<<'\n';
		return;
	}
	cout<<"impossible\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>n>>q;
	for(int i=1;i<=N*4;++i) st[i]={INF,INF};
	for(int i=1;i<=n;++i) cin>>s[i]>>e[i];
	for(int i=1;i<=n;++i) {
		nen.push_back(s[i]);
		nen.push_back(e[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	limit_size=nen.size();
	for(int i=1;i<=n;++i){
		s[i]=Find(s[i]) , e[i]=Find(e[i]);
		upd(1,1,limit_size,e[i],{s[i],i});
	}
	for(int i=1;i<=n;++i) {
		par[i][0]=Get(1,1,limit_size,s[i],e[i]).second;
	}

	for(int j=1;j<=MAXLOG;++j){
		for(int i=1;i<=n;++i) par[i][j]=par[par[i][j-1]][j-1];
	}

	while(q--){
		int l,r; cin>>l>>r;
		if (e[l]>e[r]) {
			cout<<"impossible\n";
			continue;
		}
		if (l==r){
			cout<<0<<'\n';
			continue;
		}
		if (s[r]<=e[l] && e[l]<=e[r]){
			cout<<1<<'\n';
			continue;
		}
		process(l,r);
	}
	return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:56:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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