# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
960782 | Trisanu_Das | Event Hopping (BOI22_events) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std ;
int n, q, l[100005], r[100005], bin[18][100005];
vector<int> v, s;
int bin_s(int x){
int lo = -1, hi = s.size() - 1;
while(hi - lo > 1){
int mid = (hi + lo) / 2;
if(r[s[mid]] >= x) hi = mid;
else lo = mid
}
return s[hi];
}
bool cmp(int x, int y){
if(r[x] != r[y]) return r[x] < r[y];
return l[x] < l[y];
}
int solve(int b, int x, int y){
if(b == -1) return 0;
int cur = bin[b][x];
if(l[cur] > r[y]) return (1 << b) + solve(b - 1, cur, y);
return solve(b - 1, x, y);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q ;
for(int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
v.push_back(i);
}
sort(v.begin(), v.end(), cmp);
for(int i = 1; i <= n; i++){
int u = v[i];
for(!s.empty() && l[s.back()] >= l[u]) s.pop_back();
s.push_back(u);
bin[0][u] = bin_s(u);
}
for(int i = 1; i < 18; i++) for(int j = 1; j <= n; j++) bin[i][j] = bin[i - 1][bin[i - 1][j]];
while(q--){
int x, y; cin >> x >> y;
if(l[bin[17][y]] > r[x] || r[y] < r[x]){
cout << "impossible\n"; continue;
}
if(x == y){
cout << 0 << '\n'; continue;
}
if(l[y] <= r[x]){
cout << 1 << '\n'; continue;
}
cout << 2 + solve(17, y, x) << '\n';
}
}