Submission #580899

#	Time	Username	Problem	Language	Result	Execution time	Memory
580899		amunduzbaev	Event Hopping (BOI22_events)	C++17	100 / 100	208 ms	12248 KiB

events

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int ll

const int N = 1e5 + 5;
int l[N], r[N], p[N][20];

struct ST{
	int tree[N << 2];
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			if(r[v] > r[tree[x]]) tree[x] = v;
			return;
		}
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x << 1);
		else sett(i, v, m + 1, rx, x << 1 | 1);
		if(r[tree[x << 1]] > r[tree[x << 1 | 1]]) tree[x] = tree[x << 1];
		else tree[x] = tree[x << 1 | 1];
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		int L = get(l, r, lx, m, x << 1);
		int R = get(l, r, m + 1, rx, x << 1 | 1);
		//~ cout<<::r[R]<<" "<<::r[L]<<" tree\n";
		if(::r[R] > ::r[L]) return R;
		else return L;
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	vector<int> t;
	//~ cout<<"->\n";
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		l[i] = 1e9 - l[i] + 1;
		r[i] = 1e9 - r[i] + 1;
		swap(l[i], r[i]);
		//~ cout<<l[i]<<" "<<r[i]<<"\n";
		t.push_back(l[i]);
	}
	
	sort(t.begin(), t.end());
	
	for(int i=1;i<=n;i++){
		int j = lower_bound(t.begin(), t.end(), l[i]) - t.begin();
		tree.sett(j, i);
		//~ cout<<j<<" ";
	} // cout<<"\n";
	
	for(int i=1;i<=n;i++){
		int l = lower_bound(t.begin(), t.end(), ::l[i]) - t.begin();
		int r = upper_bound(t.begin(), t.end(), ::r[i]) - t.begin() - 1;
		p[i][0] = tree.get(l, r);
		//~ cout<<l<<" "<<r<<" "<<p[i][0]<<"\n";
	}
	
	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			p[i][j] = p[p[i][j-1]][j-1];
		}
	}
	
	for(int i=0;i<q;i++){
		int a, b; cin>>b>>a;
		if(l[b] < l[a]) { cout<<"impossible\n"; continue; }
		if(a == b) { cout<<0<<"\n"; continue; }
		int res = 0;
		for(int j=19;~j;j--){
			if(r[p[a][j]] < l[b]){
				a = p[a][j];
				res += (1 << j);
			}
		}
		if(l[b] <= r[a]){
			cout<<1<<"\n";
		} else if(l[b] <= r[p[a][0]]){
			cout<<res + 2<<"\n";
		} else {
			cout<<"impossible\n";
		}
	}
}

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