Submission #901074

#	Time	Username	Problem	Language	Result	Execution time	Memory
901074		LCJLY	Event Hopping (BOI22_events)	C++14	100 / 100	463 ms	324816 KiB

events

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

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline pii combine(pii a, pii b){
	if(a.first<b.first) return a;
	return b;
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v({INT_MAX,INT_MAX}){
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void upd(int x, pii y){
		if(s==e){
			if(y.first<v.first){
				v=y;
			}
			return;
		}
		inst();
		if(x<=m)l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){	
	int n,q;
	cin >> n >> q;
	
	node st(0,1000000005);
	pii arr[n+1];
	for(int x=1;x<=n;x++){
		cin >>arr[x].first >> arr[x].second;
		st.upd(arr[x].second,{arr[x].first,x});
	}
	
	int two[25][n+5];
	memset(two,-1,sizeof(two));
	
	for(int x=1;x<=n;x++){
		pii hold=st.query(arr[x].first,arr[x].second);
		if(hold.first>=arr[x].first) continue;
		//show2(x,x,par,hold.second);
		two[0][x]=hold.second;
	}
	
	for(int x=0;x<20;x++){
		for(int y=1;y<=n;y++){
			if(two[x][y]==-1) continue;
			two[x+1][y]=two[x][two[x][y]];
		}
	}
	
	int l,r;
	for(int x=0;x<q;x++){
		cin >> l >> r;
		
		if(arr[r].second<arr[l].second){
			cout << "impossible\n";
			continue;
		}
		else if(l==r){
			cout << 0 << "\n";
			continue;
		}
		else if(arr[r].first<=arr[l].second&&arr[r].second>=arr[l].second){
			cout << 1 << "\n";
			continue;
		}
		
		int ans=0;
		for(int bit=19;bit>=0;bit--){
			if(two[bit][r]==-1) continue;
			int index=two[bit][r];
			if(arr[index].first>arr[l].second){
				ans+=1<<bit;
				r=index;
			}
		}
		//show(r,r);
		
		if(two[0][r]==-1||arr[two[0][r]].first>arr[l].second){
			cout << "impossible\n";
			continue;
		}
		
		cout << ans+2 << "\n";
	}
	
	
}	

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

		

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