oj.uz

Submission #1046560

# Submission time Handle Problem Language Result Execution time Memory
1046560 2024-08-06T16:57:37 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 114 ms 29592 KB 
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double

const int N = 5e5 + 20;
const int LOG = 21;
const int INF = 1e17;

namespace seggy{
	ar<int, 2> s[4 * N];
	
	void build(int k,int tl,int tr){
		s[k] = {-1, -1};
 		if(tl == tr)return;
		int tm = (tl + tr) / 2;
		build(k * 2, tl, tm);
		build(k *2 + 1,tm + 1, tr);
	}
	
	void upd(int k,int tl,int tr,int p,ar<int, 2> v){
		if(tl == tr){
			s[k] = max(s[k], v);
			return;
		}
		int tm = (tl + tr) / 2;
		if(p <= tm)upd(k * 2,tl, tm, p, v);
		else upd(k * 2 + 1, tm + 1, tr, p, v);
		s[k] = max(s[k * 2], s[k * 2 + 1]);
	}
	ar<int, 2> qry(int k,int tl,int tr,int l,int r){
		if(l > tr || tl > r)return {-1, -1};
		if(l <= tl && tr <= r)return s[k];
		int tm = (tl + tr) / 2;
		return max(qry(k * 2,tl, tm, l,r), qry(k *2 + 1, tm + 1, tr, l, r));
	}
}


signed main(){ios::sync_with_stdio(false);cin.tie(0);	
	int n, q;
	cin>>n>>q;
	int s[n], e[n];
	vector<int> v;
	for(int i = 0;i < n;i++){
		cin>>s[i]>>e[i];
		v.push_back(s[i]);v.push_back(e[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int m = v.size();
	seggy::build(1, 0, m - 1);
	for(int i = 0;i < n;i++){
		s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
		e[i] = lower_bound(v.begin(), v.end(), e[i]) - v.begin();
		seggy::upd(1, 0, m - 1, s[i], {e[i], i});
	}
	int up[n][LOG];
	
	for(int i = 0;i < n;i++){
		ar<int, 2> j = seggy::qry(1, 0, m-1, s[i], e[i]);
		up[i][0] = j[1];
	}
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i < n;i++){
			up[i][j] = up[up[i][j - 1]][j - 1];
		}	
	}
	
	while(q--){
		int x,y;
		cin>>x>>y;
		--x, --y;
		int ans = 0;
		for(int i = LOG - 1;i >= 0;i--){
			int j = up[x][i];
			if(j == -1)continue;
			if(e[j] < s[y]){
				x = j;
				ans |= (1 << i);
			}
		}
		if(x == y)cout<<ans<<'\n';
		else{
			if(s[y] > e[x]){
				x = up[x][0];
				++ans;
			}
			if(s[y] <= e[x] && e[x] <= e[y])cout<<ans + 1<<'\n';
			else cout<<"impossible\n";
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 103 ms 24884 KB Output is correct
3 Correct 96 ms 24888 KB Output is correct
4 Correct 112 ms 24780 KB Output is correct
5 Incorrect 103 ms 24980 KB Output isn't correct
6 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 Correct 1 ms 604 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 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 89 ms 25028 KB Output is correct
2 Correct 95 ms 24780 KB Output is correct
3 Correct 106 ms 24884 KB Output is correct
4 Correct 90 ms 29592 KB Output is correct
5 Correct 99 ms 25156 KB Output is correct
6 Correct 114 ms 29128 KB Output is correct
7 Correct 112 ms 29248 KB Output is correct
8 Correct 106 ms 29260 KB Output is correct
9 Correct 92 ms 28308 KB Output is correct
10 Correct 109 ms 28748 KB Output is correct
11 Correct 106 ms 28612 KB Output is correct
12 Correct 110 ms 28732 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 103 ms 24884 KB Output is correct
3 Correct 96 ms 24888 KB Output is correct
4 Correct 112 ms 24780 KB Output is correct
5 Incorrect 103 ms 24980 KB Output isn't correct
6 Halted 0 ms 0 KB -