Submission #775389

#	Time	Username	Problem	Language	Result	Execution time	Memory
775389		penguin133	Event Hopping (BOI22_events)	C++17	30 / 100	140 ms	24908 KiB

events

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[20][200005], n, q, S[200005], E[200005];
pi A[200005], B[200005];

void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> S[i] >> E[i];
		A[i] = {S[i], i};
		B[i] = {E[i], i};
	}
	sort(A+1, A+n+1);
	sort(B+1, B+n+1);
	int in = 1, mx = 0, idx = -1;
	for(int i=1;i<=n;i++){
		while(in <= n && A[in].fi <= B[i].fi){
			if(mx < E[A[in].se])mx = E[A[in].se], idx = A[in].se;
			in++;
		}
		if(mx > B[i].fi)par[0][B[i].se] = idx;
	}
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
	while(q--){
		int s, e; cin >> s >> e;
		if(E[s] > E[e])cout << "impossible\n";
		else if(s == e)cout << 0 << '\n';
		else if(S[e] <= E[s] && E[s] <= E[e])cout << 1 << '\n';
		else{
			int ans = 0, cur = s;
			for(int i=19;i>=0;i--){
				int x = par[i][cur];
				if(x == 0)continue;
				if(E[x] < S[e])cur = par[i][cur], ans += (1 << i);
			}
			if(par[0][cur] == 0){
				cout << "impossible\n";
				continue;
			}
			cur = par[0][cur];
			ans+=2;
			if(S[e] <= E[cur] && E[cur] <= E[e])cout << ans << '\n';
			else cout << "impossible\n";
		}
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

events.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~

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