Submission #775416

#	Time	Username	Problem	Language	Result	Execution time	Memory
775416		penguin133	Event Hopping (BOI22_events)	C++17	30 / 100	401 ms	60932 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];

struct node{
	int s, e, m, val = 1e10;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void upd(int p, int v){
		if(s == e)val = min(val, v);
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = min(l->val, r->val);
		}
	}
	int qry(int a, int b){
		if(a == s && b == e)return val;
		else if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else return min(l->qry(a, m), r->qry(m+1, b));
	}
}*root;

map <int, int> mp;
vector <int> lol;

void solve(){
	cin >> n >> q;
	root = new node(1, 2 * n);
	for(int i=1;i<=n;i++){
		cin >> S[i] >> E[i];
		A[i] = {S[i], i};
		B[i] = {E[i], i};
		lol.push_back(S[i]);
		lol.push_back(E[i]);
	}
	sort(lol.begin(), lol.end());
	int cnt = 0, prv = -1e10;
	for(auto i : lol){
		if(i == prv)continue;
		prv = i;
		mp[i] = ++cnt;
	}
	for(int i=1;i<=n;i++)root->upd(mp[E[i]], S[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;
			}
			
			ans+=2;
			if(root->qry(mp[S[e]], mp[E[e]]) <= E[cur])cout << ans << '\n';
			else {
				ans++;
				int brub = n + 1, lo = 1, hi = n;
				while (lo <= hi){
					int mid = (lo + hi) >> 1;
					if(B[mid].fi >= S[e])brub = mid, hi = mid - 1;
					else lo = mid + 1;
				}
				brub--;
				if(brub == 0)cout << "impossible\n";
				else{
					if(root->qry(mp[S[e]], mp[E[e]]) <= B[brub].fi)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:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | 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