#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void compress(vector<int> &a){
int n = a.size();
vector<pair<int,int>> b(n);
for(int i=0;i<n;i++){
b[i].first = a[i];
b[i].second = i;
}
sort(b.begin(),b.end());
a[b[0].second] = 1;
int cnt = 1;
for(int i=1;i<n;i++){
if(b[i].first == b[i-1].first){
a[b[i].second] = a[b[i-1].second];
}
else a[b[i].second] = ++cnt;
}
}
struct segTree{
int n;
vector<int> tree;
vector<int> lazy;
segTree(int _n){
n = _n;
tree.resize(4*n+5,-1);
lazy.resize(4*n+5,-1);
}
void prop(int node,int l,int r){
tree[node] = lazy[node];
if(l != r){
lazy[node<<1] = lazy[node];
lazy[node<<1|1] = lazy[node];
}
lazy[node] = -1;
}
void update(int node,int l,int r,int lQ,int rQ,int val){
if(l>r) return;
if(~lazy[node]) prop(node,l,r);
if(lQ>r || l>rQ) return;
if(lQ<=l&&r<=rQ) return lazy[node] = val, prop(node,l,r), void();
int md = l + r >> 1;
update(node<<1,l,md,lQ,rQ,val), update(node<<1|1,md+1,r,lQ,rQ,val);
tree[node] = max(tree[node<<1] , tree[node<<1|1]);
}
void update(int l,int r,int val){
update(1,1,n,l,r,val);
}
int query(int node,int l,int r,int lQ,int rQ){
if(l>r) return -1;
if(~lazy[node]) prop(node,l,r);
if(lQ>r || l>rQ) return -1;
if(lQ<=l&&r<=rQ) return tree[node];
int md = l + r >> 1;
return max(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ));
}
int query(int l,int r){
return query(1,1,n,l,r);
}
};
int sparse[200005][30], logs[200005];
void build(vector<int> &v){
int n = v.size();
for(int i=0;i<n;i++) sparse[i][0] = v[i];
for(int k=1;k<30;k++) for(int i=0;i+(1<<k)-1<n;i++)sparse[i][k] = max(sparse[i][k-1],sparse[i+(1<<k-1)][k-1]);
for(int i=2;i<=n;i++) logs[i] = logs[i>>1] + 1;
}
int query(int l,int r){
int sz = r - l + 1;
int lg = logs[sz];
return max(sparse[l][lg],sparse[r-(1<<lg)+1][lg]);
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>> v(n);
for(auto &[l,r] : v) cin>>l>>r;
vector<int> tmp;
for(auto [l,r] : v) tmp.push_back(l);
for(auto [l,r] : v) tmp.push_back(r);
compress(tmp);
for(int i=0;i<n;i++) v[i] = {tmp[i],tmp[i+n]};
segTree sg(n*2);
vector<int> lst(n);
for(int i=0;i<n;i++){
int l = v[i].first , r = v[i].second;
lst[i] = sg.query(l,r);
sg.update(l,r,i);
}
build(lst);
vector<vector<int>> P(n,vector<int>(30,1e9));
for(int i=0;i<n;i++){
int l=i+1, r = n-1;
while(l<=r){
int md = l + r >> 1;
if(query(i,md)>=i) P[i][0] = md, r = md-1;
else l = md + 1;
}
}
for(int k=1;k<30;k++){
for(int i=0;i<n;i++){
if(P[i][k-1] == 1e9) P[i][k] = 1e9;
else P[i][k] = P[P[i][k-1]][k-1];
}
}
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
a --, b --;
int node = a;
int ans = 1;
for(int k=30;k>=0;k--){
if(P[node][k] > b) continue;
node = P[node][k];
ans += (1<<k);
}
cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
Main.cpp: In member function 'void segTree::update(int, int, int, int, int, int)':
Main.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:56:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void build(std::vector<int>&)':
Main.cpp:67:104: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
67 | for(int k=1;k<30;k++) for(int i=0;i+(1<<k)-1<n;i++)sparse[i][k] = max(sparse[i][k-1],sparse[i+(1<<k-1)][k-1]);
| ~^~
Main.cpp: In function 'void solve()':
Main.cpp:79:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | for(auto &[l,r] : v) cin>>l>>r;
| ^
Main.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [l,r] : v) tmp.push_back(l);
| ^
Main.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | for(auto [l,r] : v) tmp.push_back(r);
| ^
Main.cpp:97:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | int md = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
71320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
374 ms |
74520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
71320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
