oj.uz

Submission #1046559

# Submission time Handle Problem Language Result Execution time Memory
1046559 2024-08-06T16:54:50 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 115 ms 32692 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(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 348 KB Output is correct
2 Correct 97 ms 28080 KB Output is correct
3 Correct 96 ms 28100 KB Output is correct
4 Correct 110 ms 28104 KB Output is correct
5 Incorrect 108 ms 28136 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 568 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 568 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 568 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 91 ms 28136 KB Output is correct
2 Correct 98 ms 28092 KB Output is correct
3 Correct 112 ms 28100 KB Output is correct
4 Correct 95 ms 32692 KB Output is correct
5 Correct 102 ms 28336 KB Output is correct
6 Correct 111 ms 32456 KB Output is correct
7 Correct 111 ms 32200 KB Output is correct
8 Correct 108 ms 32268 KB Output is correct
9 Correct 93 ms 30408 KB Output is correct
10 Correct 111 ms 31936 KB Output is correct
11 Correct 115 ms 31764 KB Output is correct
12 Correct 110 ms 32008 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 97 ms 28080 KB Output is correct
3 Correct 96 ms 28100 KB Output is correct
4 Correct 110 ms 28104 KB Output is correct
5 Incorrect 108 ms 28136 KB Output isn't correct
6 Halted 0 ms 0 KB -