#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define ll long long
vector<vector<ll>> lift;
ll findLift(ll from, ll mn){
ll i = 0;
ll par = 1;
while(lift[from][i] <= mn) i++, par*=2;
return par/2 + (i>0?findLift(lift[from][i-1], mn):0);
}
int main(void){
//freopen("input.txt", "r", stdin);
vector<pair<ll, ll>> h;
ll n;
cin>>n;
h.assign(n, {});
for(ll i = 0; i<n; i++) cin>>h[i].first>>h[i].second;
vector<ll> step(n, 0);
set<pair<ll, pair<ll, ll>>> s;
ll nextSt = n;
ll p2 = n;
for(ll i = n-1; i>=0; i--){
auto e = s.lower_bound({h[i].first, {0, 0}});
while(e!=s.end() && e->first <= h[i].second){
p2--;
s.erase({h[p2].first, {h[p2].second, p2}});
e = s.lower_bound({h[i].first, {0, 0}});
}
while( e!= s.begin() && prev(e)->second.first >= h[i].first){
p2--;
s.erase({h[p2].first, {h[p2].second, p2}});
e = s.lower_bound({h[i].first, {0, 0}});
}
s.insert({h[i].first, {h[i].second, i}});
step[i] = p2;
}
lift.assign(n+1, vector<ll>(40, -1));
for(ll i = 0; i<40; i++) lift[n][i] = n;
for(ll i = 0; i<n; i++) lift[i][0] = step[i];
for(ll i = n-1; i>=0; i--){
for(ll j = 1; j<40; j++){
lift[i][j] = lift[lift[i][j-1]][j-1];
}
}
ll q;
cin>>q;
for(ll i = 0; i<q; i++){
ll l, r;
cin>>l>>r;
cout<<findLift(l-1, r-1)+1<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |