Submission #1046563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046563		vjudge1	Event Hopping (BOI22_events)	C++17	100 / 100	128 ms	32712 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double

const int N = 5e5 + 20;
const int LOG = 21;
const int INF = 1e17;

namespace seggy{
	ar<int, 2> s[4 * N];
	
	void build(int k,int tl,int tr){
		s[k] = {INF, -1};
 		if(tl == tr)return;
		int tm = (tl + tr) / 2;
		build(k * 2, tl, tm);
		build(k *2 + 1,tm + 1, tr);
	}
	
	void upd(int k,int tl,int tr,int p,ar<int, 2> v){
		if(tl == tr){
			s[k] = min(s[k], v);
			return;
		}
		int tm = (tl + tr) / 2;
		if(p <= tm)upd(k * 2,tl, tm, p, v);
		else upd(k * 2 + 1, tm + 1, tr, p, v);
		s[k] = min(s[k * 2], s[k * 2 + 1]);
	}
	ar<int, 2> qry(int k,int tl,int tr,int l,int r){
		if(l > tr || tl > r)return {INF, -1};
		if(l <= tl && tr <= r)return s[k];
		int tm = (tl + tr) / 2;
		return min(qry(k * 2,tl, tm, l,r), qry(k *2 + 1, tm + 1, tr, l, r));
	}
}


signed main(){ios::sync_with_stdio(false);cin.tie(0);	
	int n, q;
	cin>>n>>q;
	int s[n], e[n];
	vector<int> v;
	for(int i = 0;i < n;i++){
		cin>>s[i]>>e[i];
		v.push_back(s[i]);v.push_back(e[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int m = v.size();
	seggy::build(1, 0, m - 1);
	for(int i = 0;i < n;i++){
		s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
		e[i] = lower_bound(v.begin(), v.end(), e[i]) - v.begin();
		seggy::upd(1, 0, m - 1, e[i], {s[i], i});
	}
	int up[n][LOG];
	
	for(int i = 0;i < n;i++){
		ar<int, 2> j = seggy::qry(1, 0, m-1, s[i], e[i]);
		up[i][0] = j[1];
	}
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i < n;i++){
			up[i][j] = up[up[i][j - 1]][j - 1];
		}	
	}
	
	while(q--){
		int x,y;
		cin>>x>>y;
		--x, --y;
		int ans = 0;
		for(int i = LOG - 1;i >= 0;i--){
			int j = up[y][i];
			if(j == -1)continue;
			if(s[j] > e[x]){
				y = j;
				ans += (1 << i);
			}
		}
		if(x == y)cout<<ans<<'\n';
		else{
			if(s[y] > e[x]){
				y = up[y][0];
				++ans;
			}
			if(s[y] <= e[x] && e[x] <= e[y])cout<<ans + 1<<'\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