Submission #854671

#	Time	Username	Problem	Language	Result	Execution time	Memory
854671		PoPularPlusPlus	Event Hopping (BOI22_events)	C++17	30 / 100	111 ms	17352 KiB

events

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

#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 998244353;

const int MX = 1000000005;
const int L = 20;

struct Seg {
	int siz;
	vector<pair<int,int>> v;

	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		v.assign(siz*2,mp(MX,-1));
	}

	pair<int,int> merge(pair<int,int> x , pair<int,int> y){
		pair<int,int> res;
		res.vf = min(x.vf , y.vf);
		if(x.vf == y.vf)res.vs = min(x.vs , y.vs);
		else if(res.vf == x.vf)res.vs = x.vs;
		else res.vs = y.vs;
		return res;
	}

	void set(int i , pair<int,int> p , int x , int lx , int rx){
		if(rx - lx == 1){
			v[x] = merge(p,v[x]);
			return;
		}
		int m = (lx + rx)/2;
		if(i < m)
			set(i , p , 2 * x + 1 , lx , m);
		else 
			set(i , p , 2 * x + 2 , m , rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}

	void set(int i , pair<int,int> p){
		set(i , p , 0 , 0 , siz);
	}

	pair<int,int> range_mx(int l , int r , int x , int lx , int rx){
		if(l >= rx || lx >= r)return mp(MX,-1);
		if(lx >= l && rx <= r)return v[x];
		int m = (lx + rx)/2;
		return merge(range_mx(l,r,2*x+1,lx,m),range_mx(l,r,2*x+2,m,rx));
	}

	pair<int,int> range_mx(int l , int r){
		return range_mx(l , r , 0 , 0 , siz);
	}
};

void solve(){
	int n , q;
	cin >> n >> q;
	vector<pair<int,int>> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i].vf >> v[i].vs;
	}

	// positions acocrding to sorted e

	vector<pair<int,pair<int,int>>> e_sort;
	//vector<pair<int,pair<int,int>>> rev;

	for(int i = 0; i < n; i++){
		e_sort.pb(mp(v[i].vs , mp(v[i].vf,i)));
	}
	sort(all(e_sort));
	//rev = e_sort;
	//reverse(all(rev));
	int pos[n];
	for(int i = 0; i < n; i++){
		pos[e_sort[i].vs.vs] = i;
	}

	// segtree 

	Seg st;
	st.init(n + 1);
	for(int i = n - 1; i >= 0; i--){
		st.set(i,mp(e_sort[i].vs.vf , i));
	}

	// binary lifting

	int up[n][L];
	int p[n];
	for(int i = 0; i < n; i++){
		pair<int,pair<int,int>> tp = mp(e_sort[i].vs.vf , mp(-1 , -1));
		int left = (lower_bound(all(e_sort),tp) - e_sort.begin());
		if(left == i)
			up[i][0] = p[i] = i;
		else {
			p[i] = st.range_mx(left,i).vs;
			//cout << left << ' ' << st.range_mx(left,i).vf << ' ' << p[i] << '\n';
			up[i][0] = left;
		}
	}
	for(int j = 1; j < L; j++){
		for(int i = 0; i < n; i++){
			if(j == 1)
				up[i][j] = up[p[i]][j-1];
			else 
				up[i][j] = up[up[i][j-1]][j-1];
		}
	}

	// answering the queries 

	while(q--){
		int s , e;
		cin >> s >> e;
		s--;
		e--;
		if(s == e){
			cout << 0 << '\n';
			continue;
		}
		int ogs = pos[s]  , oge = pos[e];
		if(ogs > oge){
			if(v[s].vs >= v[e].vf && v[s].vs <= v[e].vs){
				cout << 1 << '\n';
				continue;
			}
			else {
				cout << "impossible\n";
				continue;
			}
		}
		int i = oge;
		int ans = 0;
		for(int j = L-1; j >= 0; j--){
			if(up[i][j] > ogs){
				ans += (1<<j);
				i = up[i][j];
			}
		}
		if(i > ogs){
			i = up[i][0];
			ans++;
		}
		if(i > ogs)
			cout << "impossible\n";
		else 
			cout << ans << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin >> t;
	//while(t--)
		solve();
	return 0;
}

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