Submission #1076629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076629		AlphaBruh	Event Hopping (BOI22_events)	C++17	100 / 100	70 ms	14796 KiB

events

#include<bits/stdc++.h>
using namespace std;
#define SIZE 100005
struct rg{
	int id,l,r;
	bool operator<(rg x){
		if(r!=x.r) return r<x.r;
		return l<x.l;
	}
}rgs[SIZE];
int n,q;
int arr[SIZE];
int lb(int x){return x&-x;}
int minl(int a, int b){return rgs[a].l<rgs[b].l?a:b;}
void edit(int loc, int v){
	while(loc<=n){
		arr[loc]=minl(arr[loc],v);
		loc+=lb(loc);
	}
}
int get(int loc){
	int ret=0;
	while(loc){
		ret=minl(ret,arr[loc]);
		loc-=lb(loc);
	}
	return ret;
}
int rid[SIZE];
int irg[SIZE];
int bz[20][SIZE];
void cal(int id){
	int l=1,r=id,md;
	while(l<r){
		md=(l+r)>>1;
		if(rgs[md].r<rgs[id].l) l=md+1;
		else r=md;
	}
	if(r==id) bz[0][id]=id;
	else bz[0][id]=get(n-r+1);
	irg[id]=r;
	edit(n-id+1,id);
}
int PID;
int build(){
	int pid,p;
	for(pid=1,p=2;p<=n;p<<=1,pid++){
		for(int i=1;i<=n;i++){
			bz[pid][i]=bz[pid-1][bz[pid-1][i]];
		}
	}
	return pid;
}
void query(){
	int u,a;
	cin>>u>>a;
	a=rid[a];
	u=rid[u];
	if(rgs[a].r==rgs[u].r){
		printf("%d\n",int(a!=u));
		return;
	}
	if(a<u){
		printf("impossible\n");
		return;
	}
	int cnt=0;
	for(int pid=PID,p=1<<PID;pid>=0;pid--,p>>=1){
		if(u<irg[bz[pid][a]]){
			a=bz[pid][a];
			cnt+=p;
		}
	}
	if(irg[a]<=u){
		printf("1\n");
		return;
	}
	a=bz[0][a];
	if(u < irg[a]) printf("impossible\n");
	else printf("%d\n",cnt+2);
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		rgs[i].id=i;
		cin>>rgs[i].l>>rgs[i].r;
	}
	sort(rgs+1,rgs+1+n);
	rgs[0].l=2e9;
	for(int i=1;i<=n;i++){
		rid[rgs[i].id]=i;
		cal(i);
	}
	PID=build();
	while(q--) query();
}

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