Submission #1123691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123691		peacebringer1667	Event Hopping (BOI22_events)	C++17	30 / 100	76 ms	15932 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];
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;
}

void prepare(int n,int q){
	sort(a + 1,a + 1 + n);
	for (int i = 1 ; i <= n ; i++) pos[a[i].id] = i;
	
	set <pir,greater<pir>> s;
	
	for (int i = n ; i > 0 ; i--){
	    int R = a[i].r;
		
		while (s.size() && a[(*s.begin()).se].l > R) s.erase(s.begin());
		
		if (s.size()){
			int nxt = (*s.begin()).se;
			
			spt[i][0] = nxt;
			for (int j = 1 ; j <= alp ; j++)
			    spt[i][j] = spt[spt[i][j - 1]][j - 1];
		}	
		
		s.insert({R,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[u][i] > 0 && spt[u][i] <= v){
	    	res += (1 << i);
	    	u = spt[u][i];
		}
	
	if (u >= v) return res;
	if (a[v].l <= a[u].r && a[u].r <= a[v].r) return res + 1;
	return -1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30