Submission #1123708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123708		peacebringer1667	Event Hopping (BOI22_events)	C++17	100 / 100	80 ms	11716 KiB

events

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;
const int alp = 17;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

struct CTDL{
	int l = 0,r = 0,id = 0;
	bool operator <(const CTDL&other) const{
		return (r < other.r) || (r == other.r && l < other.l);
	}
};

CTDL a[maxn];
pir Q[maxn];
vector <int> lst;
int pos[maxn],spt[maxn][alp + 2];

void input(int n,int q){
	for (int i = 1 ; i <= n ; i++) cin >> a[i].l >> a[i].r,a[i].id = i;
	for (int i = 1 ; i <= q ; i++) cin >> Q[i].fi >> Q[i].se;
}

int get_min(int L){
	if (!lst.size()) return 0;
	int l = 0,r = lst.size() - 1,ans = 0;
	while (l <= r){
		int w = (l + r)/2;
		if (a[lst[w]].r >= L){
			ans = lst[w];
			r = w - 1;
		}
		else l = w + 1;
	}
	return ans;
}

void prepare(int n,int q){
	sort(a + 1,a + 1 + n);
	for (int i = 1 ; i <= n ; i++) pos[a[i].id] = i;
	
	for (int i = 1 ; i <= n ; i++){
	    int nxt = get_min(a[i].l);
	    
	    if (nxt > 0){
	    	spt[i][0] = nxt;
	    	for (int j = 1 ; j <= alp ; j++)
	    	    spt[i][j] = spt[spt[i][j - 1]][j - 1];
		}
		
		while (lst.size() && a[lst.back()].l >= a[i].l) lst.pop_back();
		lst.push_back(i);
	}
}

int answer_query(int x,int y,int n){
	if (x == y) return 0;
	int u = pos[x],v = pos[y],res = 0;
	
	if (a[u].r > a[v].r) return -1;
	if (a[u].r == a[v].r) return 1;
	
    for (int i = alp ; i >= 0 ; i--){
    	if (spt[v][i] > 0 && a[spt[v][i]].l > a[u].r){
    		res += (1 << i);
    		v = spt[v][i];
		}
	}
	
	if (a[v].l <= a[u].r && a[v].r >= a[u].r) return 1;
	
	if (spt[v][0] == 0) return -1;
	res++;v = spt[v][0];
	
	if (v <= u) return res;
	
	if (a[v].l <= a[u].r && a[v].r >= a[u].r) return res + 1;
	
	return -1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
// 	freopen("in.txt","r",stdin);
// 	freopen("out.out","w",stdout);
	
	int n,q;
	cin >> n >> q;
	input(n,q);
	
	prepare(n,q);
	
	for (int i = 1 ; i <= q ; i++){
		int r = answer_query(Q[i].fi,Q[i].se,n);
		
		if (r > -1) cout << r << "\n";
		if (r == -1) cout << "impossible" << "\n";
	}

	return 0;
}

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