oj.uz

Submission #853445

# Submission time Handle Problem Language Result Execution time Memory
853445 2023-09-24T11:06:56 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 365 ms 37672 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);
	}
};

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;
		}
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 272 ms 37672 KB Output is correct
3 Correct 365 ms 37336 KB Output is correct
4 Incorrect 324 ms 37328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 37384 KB Output is correct
2 Correct 289 ms 37492 KB Output is correct
3 Incorrect 312 ms 37396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 272 ms 37672 KB Output is correct
3 Correct 365 ms 37336 KB Output is correct
4 Incorrect 324 ms 37328 KB Output isn't correct
5 Halted 0 ms 0 KB -