oj.uz

Submission #853413

# Submission time Handle Problem Language Result Execution time Memory
853413 2023-09-24T09:45:39 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 124 ms 22776 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

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> original_start(N);
	vector<pair<int, int>> S(N);
	for(int i = 0; i < N; i++) {cin >> S[i].first >> E[i]; S[i].second = i; original_start[i] = S[i].first;}
	vector<pair<int, int>> adj(N); //Order by E[i], then by i.
	set<pair<int,int>> s;
	sort(S.begin(), S.end());
	for(pair<int, int> p : S){
		while((int)s.size() > 0 && (*s.begin()).first < p.first){
			pair<int, int> pr = *s.begin(); s.erase(s.begin());
			pair<int, int> pr1 = {-1, -1};
			if((int)s.size() > 0) pr1 = *s.rbegin();
			adj[pr.second] = max(pr1, pr);
		}
		s.insert({E[p.second], p.second});
	}
	while((int)s.size() > 0){
		pair<int, int> pr = *s.begin(); s.erase(s.begin());
		pair<int, int> pr1 = {-1, -1};
		if((int)s.size() > 0) pr1 = *s.rbegin();
		adj[pr.second] = max(pr1, pr);
	}
	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];
			}
		}
	}
	while(Q--){
		int s, e; cin >> s >> e; s--; e--;
		if(s == e){
			cout << 0 << endl;
			continue;
		}
		int ans = 0;
		for(int k = 19; k >= 0; k--){
			pair<int, int> pr = {E[e], e};
			if(dp[k][s] < pr){
				s = dp[k][s].second;
				ans += (1 << k);
			}
		}
		ans++;
		if(can_reach(s, e, original_start, E)) cout << ans << endl;
		else cout << "impossible" << endl;
	}
}

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

	solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 60 ms 22340 KB Output is correct
3 Correct 84 ms 22208 KB Output is correct
4 Correct 124 ms 22108 KB Output is correct
5 Correct 100 ms 22284 KB Output is correct
6 Correct 84 ms 22208 KB Output is correct
7 Incorrect 83 ms 22100 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Incorrect 1 ms 604 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Incorrect 1 ms 604 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Incorrect 1 ms 604 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 69 ms 22164 KB Output is correct
2 Correct 88 ms 22080 KB Output is correct
3 Correct 114 ms 22080 KB Output is correct
4 Correct 106 ms 22472 KB Output is correct
5 Correct 106 ms 22336 KB Output is correct
6 Correct 117 ms 22332 KB Output is correct
7 Correct 92 ms 22112 KB Output is correct
8 Correct 84 ms 22336 KB Output is correct
9 Correct 48 ms 21136 KB Output is correct
10 Correct 83 ms 21964 KB Output is correct
11 Correct 85 ms 22776 KB Output is correct
12 Correct 97 ms 21828 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 60 ms 22340 KB Output is correct
3 Correct 84 ms 22208 KB Output is correct
4 Correct 124 ms 22108 KB Output is correct
5 Correct 100 ms 22284 KB Output is correct
6 Correct 84 ms 22208 KB Output is correct
7 Incorrect 83 ms 22100 KB Output isn't correct
8 Halted 0 ms 0 KB -