Submission #1263527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263527		altern23	Event Hopping (BOI22_events)	C++20	100 / 100	149 ms	84604 KiB

events

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 4e18;
const int MOD = 998244353;

ll S[MAXN + 5], E[MAXN + 5], lg[MAXN + 5], up[MAXN + 5][20];
pii sp[MAXN + 5][20];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(int i = 2; i <= MAXN; i++){
		lg[i] = lg[i / 2] + 1;
	}
	for(;tc--;){
		ll N, Q; cin >> N >> Q;
		vector<ll> comp;
		for(int i = 1; i <= N; i++){
			cin >> S[i] >> E[i];
			comp.push_back(S[i]), comp.push_back(E[i]);
		}
		
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		
		ll M = comp.size();
		for(int i = 1; i <= M; i++) sp[i][0] = {INF, INF};
		
		for(int i = 1; i <= N; i++){
			S[i] = lower_bound(comp.begin(), comp.end(), S[i]) - comp.begin() + 1;
			E[i] = lower_bound(comp.begin(), comp.end(), E[i]) - comp.begin() + 1;
			sp[E[i]][0] = min(sp[E[i]][0], {S[i], i});
		}
		
		for(int log = 1; log < 20; log++){
			for(int i = 1; i <= M - (1LL << (log - 1)); i++) sp[i][log] = min(sp[i][log - 1], sp[i + (1LL << (log - 1))][log - 1]);
		}
		
		auto query = [&](ll l, ll r){
			return min(sp[l][lg[r - l + 1]], sp[r - (1LL << lg[r - l + 1]) + 1][lg[r - l + 1]]);
		};
		
		for(int i = 1; i <= N; i++){
			up[i][0] = query(S[i], E[i]).sec;
		}
		
		for(int log = 1; log < 20; log++){
			for(int i = 1; i <= N; i++){
				up[i][log] = up[up[i][log - 1]][log - 1];
			}
		}
		
		for(int i = 1; i <= Q; i++){
			ll a, b; cin >> a >> b;
			if(a == b){
				cout << 0 << "\n";
				continue;
			}
			if(E[b] < E[a]){
				cout << "impossible\n";
				continue;
			}
			if(S[b] <= E[a] && E[a] <= E[b]){
				cout << 1 << "\n";
				continue;
			}
			
			ll cur = b, dist = 0;
			bool ok = 0;
			for(int log = 19; log >= 0; --log){
				if(S[up[cur][log]] > E[a]){
					dist += (1LL << log);
					cur = up[cur][log];
				}
				else{
					ok = 1;
				}
			}
			
			if(!ok) cout << "impossible\n";
			else cout << dist + 2 << "\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