oj.uz

Submission #775416

# Submission time Handle Problem Language Result Execution time Memory
775416 2023-07-06T11:22:23 Z penguin133 Event Hopping (BOI22_events) C++17
30 / 100
 401 ms 60932 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 195 ms 54188 KB Output is correct
3 Correct 209 ms 54288 KB Output is correct
4 Correct 299 ms 54184 KB Output is correct
5 Correct 240 ms 54924 KB Output is correct
6 Correct 237 ms 55540 KB Output is correct
7 Correct 232 ms 55756 KB Output is correct
8 Correct 285 ms 60932 KB Output is correct
9 Correct 261 ms 60232 KB Output is correct
10 Correct 230 ms 54608 KB Output is correct
11 Correct 276 ms 57092 KB Output is correct
12 Correct 92 ms 53936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Incorrect 2 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Incorrect 2 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Incorrect 2 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 54168 KB Output is correct
2 Correct 236 ms 54176 KB Output is correct
3 Correct 319 ms 54220 KB Output is correct
4 Correct 256 ms 60192 KB Output is correct
5 Correct 291 ms 54596 KB Output is correct
6 Correct 401 ms 60612 KB Output is correct
7 Correct 400 ms 60668 KB Output is correct
8 Correct 347 ms 60756 KB Output is correct
9 Correct 179 ms 59944 KB Output is correct
10 Correct 309 ms 60280 KB Output is correct
11 Correct 265 ms 60072 KB Output is correct
12 Correct 308 ms 60364 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 195 ms 54188 KB Output is correct
3 Correct 209 ms 54288 KB Output is correct
4 Correct 299 ms 54184 KB Output is correct
5 Correct 240 ms 54924 KB Output is correct
6 Correct 237 ms 55540 KB Output is correct
7 Correct 232 ms 55756 KB Output is correct
8 Correct 285 ms 60932 KB Output is correct
9 Correct 261 ms 60232 KB Output is correct
10 Correct 230 ms 54608 KB Output is correct
11 Correct 276 ms 57092 KB Output is correct
12 Correct 92 ms 53936 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 980 KB Output is correct
16 Correct 1 ms 1024 KB Output is correct
17 Incorrect 2 ms 980 KB Output isn't correct
18 Halted 0 ms 0 KB -