oj.uz

Submission #853451

# Submission time Handle Problem Language Result Execution time Memory
853451 2023-09-24T11:15:55 Z vjudge1 Event Hopping (BOI22_events) C++17
100 / 100
 468 ms 50312 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

struct segTree{
	vector<pair<int, int>> mn;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		mn.assign(2 * sz, {2e9, 2e9});
	}
	void set(int i, pair<int, int> val, int x, int lx, int rx){
		if(rx - lx == 1){
			mn[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set(i, val, 2 * x + 1, lx, m);
		else set(i, val, 2 * x + 2, m, rx);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
	}
	void set(int i, pair<int, int> val){
		set(i, val, 0, 0, sz);
	}
	pair<int, int> calc(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r) return mn[x];
		else if(lx >= r || rx <= l) return {2e9, 2e9};
		int m = (lx + rx) / 2;
		pair<int, int> p1 = calc(l, r, 2 * x + 1, lx, m);
		pair<int, int> p2 = calc(l, r, 2 * x + 2, m, rx);
		return min(p1, p2);
	}
	pair<int, int> calc(int l, int r){
		return calc(l, r, 0, 0, sz);
	}
};

bool can_reach(int i, int j, vector<int>& S, vector<int>& E){
	if(S[j] <= E[i] && E[i] <= E[j]) return true;
	else return false;
}

void solve(){
	int N, Q; cin >> N >> Q;
	vector<int> E(N);
	vector<int> S(N);
	vector<int> all;
	for(int i = 0; i < N; i++) {cin >> S[i] >> E[i]; all.push_back(S[i]); all.push_back(E[i]);}
	sort(all.begin(), all.end());
	int curr = 0;
	int lst_x = -1;
	map<int, int> frst;
	map<int, int> lst;
	for(int x : all){
		bool fst = 0;
		if(x != lst_x) fst = 1;
		lst_x = x;
		lst[x] = curr;
		if(fst) frst[x] = curr;
		curr++;
	}
	map<int, int> add;
	segTree st; st.init(2 * N);
	for(int i = 0; i < N; i++){
		st.set(frst[E[i]] + add[E[i]], {S[i], i});
		add[E[i]]++;
	}
	vector<pair<int, int>> adj(N); //Order by E[i], then by i.
	for(int i = 0; i < N; i++){
		adj[i] = st.calc(frst[S[i]], lst[E[i]] + 1);
	}
	vector<vector<pair<int, int>>> dp(20, vector<pair<int, int>>(N));
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) dp[k][i] = adj[i];
			else{
				dp[k][i] = dp[k-1][dp[k-1][i].second];
			}
		}
	}
	// for(int i = 0; i < N; i++){
	// 	cout << "i " << i << " adj " << adj[i].first << " " << adj[i].second << endl;
	// }
	// for(int k = 0; k < 3; k++){
	// 	cout << "k " << k << endl;
	// 	for(int i = 0; i < N; i++){
	// 		cout << "i " << i << " " << dp[k][i].first << " " << dp[k][i].second << endl;
	// 	}
	// }
	while(Q--){
		int s, e; cin >> s >> e; s--; e--;
		if(s == e){
			cout << 0 << endl;
			continue;
		}else if(can_reach(s, e, S, E)){
			cout << 1 << endl;
			continue;
		}
		int orge = e;
		int ans = -1;
		int curr = 0;
		for(int k = 19; k >= 0; k--){
			if(dp[k][e].first > E[s]){
				e = dp[k][e].second;
				curr += (1 << k);
			}else ans = curr + (1 << k);
		}
		if(ans != -1 && E[s] <= E[orge]) cout << ans + 1 << endl;
		else cout << "impossible" << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 290 ms 37384 KB Output is correct
3 Correct 292 ms 37564 KB Output is correct
4 Correct 361 ms 37300 KB Output is correct
5 Correct 306 ms 38408 KB Output is correct
6 Correct 309 ms 39064 KB Output is correct
7 Correct 324 ms 39404 KB Output is correct
8 Correct 401 ms 50276 KB Output is correct
9 Correct 404 ms 50200 KB Output is correct
10 Correct 294 ms 40636 KB Output is correct
11 Correct 414 ms 44340 KB Output is correct
12 Correct 152 ms 37688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 600 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 36 ms 3844 KB Output is correct
20 Correct 32 ms 3664 KB Output is correct
21 Correct 34 ms 4348 KB Output is correct
22 Correct 34 ms 3924 KB Output is correct
23 Correct 29 ms 4504 KB Output is correct
24 Correct 28 ms 4432 KB Output is correct
25 Correct 37 ms 3920 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 800 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 241 ms 39372 KB Output is correct
20 Correct 237 ms 38604 KB Output is correct
21 Correct 249 ms 37068 KB Output is correct
22 Correct 282 ms 42788 KB Output is correct
23 Correct 326 ms 48720 KB Output is correct
24 Correct 336 ms 48588 KB Output is correct
25 Correct 41 ms 24608 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 37440 KB Output is correct
2 Correct 277 ms 37432 KB Output is correct
3 Correct 342 ms 37352 KB Output is correct
4 Correct 399 ms 47188 KB Output is correct
5 Correct 310 ms 37564 KB Output is correct
6 Correct 439 ms 46796 KB Output is correct
7 Correct 378 ms 46796 KB Output is correct
8 Correct 427 ms 46832 KB Output is correct
9 Correct 319 ms 46796 KB Output is correct
10 Correct 380 ms 46760 KB Output is correct
11 Correct 377 ms 46796 KB Output is correct
12 Correct 382 ms 46796 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 290 ms 37384 KB Output is correct
3 Correct 292 ms 37564 KB Output is correct
4 Correct 361 ms 37300 KB Output is correct
5 Correct 306 ms 38408 KB Output is correct
6 Correct 309 ms 39064 KB Output is correct
7 Correct 324 ms 39404 KB Output is correct
8 Correct 401 ms 50276 KB Output is correct
9 Correct 404 ms 50200 KB Output is correct
10 Correct 294 ms 40636 KB Output is correct
11 Correct 414 ms 44340 KB Output is correct
12 Correct 152 ms 37688 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 2 ms 856 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 2 ms 856 KB Output is correct
29 Correct 2 ms 856 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 36 ms 3844 KB Output is correct
32 Correct 32 ms 3664 KB Output is correct
33 Correct 34 ms 4348 KB Output is correct
34 Correct 34 ms 3924 KB Output is correct
35 Correct 29 ms 4504 KB Output is correct
36 Correct 28 ms 4432 KB Output is correct
37 Correct 37 ms 3920 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 2 ms 600 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 2 ms 800 KB Output is correct
43 Correct 2 ms 600 KB Output is correct
44 Correct 2 ms 856 KB Output is correct
45 Correct 2 ms 856 KB Output is correct
46 Correct 1 ms 600 KB Output is correct
47 Correct 241 ms 39372 KB Output is correct
48 Correct 237 ms 38604 KB Output is correct
49 Correct 249 ms 37068 KB Output is correct
50 Correct 282 ms 42788 KB Output is correct
51 Correct 326 ms 48720 KB Output is correct
52 Correct 336 ms 48588 KB Output is correct
53 Correct 41 ms 24608 KB Output is correct
54 Correct 267 ms 37440 KB Output is correct
55 Correct 277 ms 37432 KB Output is correct
56 Correct 342 ms 37352 KB Output is correct
57 Correct 399 ms 47188 KB Output is correct
58 Correct 310 ms 37564 KB Output is correct
59 Correct 439 ms 46796 KB Output is correct
60 Correct 378 ms 46796 KB Output is correct
61 Correct 427 ms 46832 KB Output is correct
62 Correct 319 ms 46796 KB Output is correct
63 Correct 380 ms 46760 KB Output is correct
64 Correct 377 ms 46796 KB Output is correct
65 Correct 382 ms 46796 KB Output is correct
66 Correct 1 ms 344 KB Output is correct
67 Correct 252 ms 40380 KB Output is correct
68 Correct 305 ms 40392 KB Output is correct
69 Correct 347 ms 40380 KB Output is correct
70 Correct 316 ms 41332 KB Output is correct
71 Correct 325 ms 42352 KB Output is correct
72 Correct 325 ms 42428 KB Output is correct
73 Correct 398 ms 50312 KB Output is correct
74 Correct 429 ms 50108 KB Output is correct
75 Correct 324 ms 40624 KB Output is correct
76 Correct 352 ms 44396 KB Output is correct
77 Correct 149 ms 37564 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 2 ms 600 KB Output is correct
80 Correct 2 ms 600 KB Output is correct
81 Correct 1 ms 604 KB Output is correct
82 Correct 2 ms 604 KB Output is correct
83 Correct 2 ms 856 KB Output is correct
84 Correct 2 ms 856 KB Output is correct
85 Correct 1 ms 600 KB Output is correct
86 Correct 33 ms 4176 KB Output is correct
87 Correct 32 ms 3664 KB Output is correct
88 Correct 35 ms 3920 KB Output is correct
89 Correct 32 ms 3972 KB Output is correct
90 Correct 29 ms 4432 KB Output is correct
91 Correct 29 ms 4432 KB Output is correct
92 Correct 30 ms 3920 KB Output is correct
93 Correct 233 ms 39376 KB Output is correct
94 Correct 291 ms 38500 KB Output is correct
95 Correct 255 ms 36812 KB Output is correct
96 Correct 264 ms 42876 KB Output is correct
97 Correct 358 ms 48972 KB Output is correct
98 Correct 345 ms 48588 KB Output is correct
99 Correct 40 ms 24700 KB Output is correct
100 Correct 468 ms 49852 KB Output is correct
101 Correct 434 ms 49852 KB Output is correct
102 Correct 394 ms 50120 KB Output is correct
103 Correct 382 ms 49432 KB Output is correct
104 Correct 372 ms 49340 KB Output is correct
105 Correct 400 ms 49436 KB Output is correct
106 Correct 276 ms 36328 KB Output is correct
107 Correct 330 ms 39780 KB Output is correct
108 Correct 315 ms 38000 KB Output is correct
109 Correct 304 ms 38132 KB Output is correct
110 Correct 401 ms 49692 KB Output is correct
111 Correct 430 ms 49604 KB Output is correct