oj.uz

Submission #775400

# Submission time Handle Problem Language Result Execution time Memory
775400 2023-07-06T11:02:11 Z penguin133 Event Hopping (BOI22_events) C++17
30 / 100
 458 ms 60984 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 = 1e9;
	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 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:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 204 ms 54200 KB Output is correct
3 Correct 256 ms 54200 KB Output is correct
4 Correct 254 ms 54200 KB Output is correct
5 Correct 229 ms 54956 KB Output is correct
6 Correct 251 ms 55524 KB Output is correct
7 Correct 224 ms 55732 KB Output is correct
8 Correct 268 ms 60984 KB Output is correct
9 Correct 221 ms 60200 KB Output is correct
10 Correct 245 ms 54552 KB Output is correct
11 Correct 273 ms 57224 KB Output is correct
12 Correct 108 ms 53936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 980 KB Output is correct
5 Incorrect 1 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 0 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 980 KB Output is correct
5 Incorrect 1 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 0 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 980 KB Output is correct
5 Incorrect 1 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 210 ms 54180 KB Output is correct
2 Correct 260 ms 54196 KB Output is correct
3 Correct 283 ms 54200 KB Output is correct
4 Correct 255 ms 60216 KB Output is correct
5 Correct 238 ms 54584 KB Output is correct
6 Correct 458 ms 60632 KB Output is correct
7 Correct 384 ms 60584 KB Output is correct
8 Correct 331 ms 60896 KB Output is correct
9 Correct 178 ms 59828 KB Output is correct
10 Correct 296 ms 60228 KB Output is correct
11 Correct 283 ms 60132 KB Output is correct
12 Correct 296 ms 60300 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 204 ms 54200 KB Output is correct
3 Correct 256 ms 54200 KB Output is correct
4 Correct 254 ms 54200 KB Output is correct
5 Correct 229 ms 54956 KB Output is correct
6 Correct 251 ms 55524 KB Output is correct
7 Correct 224 ms 55732 KB Output is correct
8 Correct 268 ms 60984 KB Output is correct
9 Correct 221 ms 60200 KB Output is correct
10 Correct 245 ms 54552 KB Output is correct
11 Correct 273 ms 57224 KB Output is correct
12 Correct 108 ms 53936 KB Output is correct
13 Correct 0 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 980 KB Output is correct
17 Incorrect 1 ms 980 KB Output isn't correct
18 Halted 0 ms 0 KB -