#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5, B = 17;
int mn[B+5][MAXN*4], mx[B+5][MAXN*4], lzmn[MAXN*4], lzmx[MAXN*4];
void build(int node, int l, int r){
lzmn[node] = MAXN;
if(l == r){
mn[0][node] = l; mx[0][node] = l;
return;
}
int mid = (l+r)/2 , e =node*2, d = node*2+1;
build(e,l,mid); build(d,mid+1,r);
mn[0][node] = min(mn[0][e],mn[0][d]); mx[0][node] = max(mx[0][e],mx[0][d]);
}
void refresh(int node, int l, int r){
mn[0][node] = min(mn[0][node],lzmn[node]); mx[0][node] = max(mx[0][node],lzmx[node]);
if(l != r){
lzmn[node*2] = min(lzmn[node*2], lzmn[node]); lzmn[node*2+1] = min(lzmn[node*2+1], lzmn[node]);
lzmx[node*2] = max(lzmx[node*2], lzmx[node]); lzmx[node*2+1] = max(lzmx[node*2+1], lzmx[node]);
}
lzmn[node] = MAXN; lzmx[node] = 0;
}
void update(int node, int l, int r, int i, int j, int t, int x){
refresh(node,l,r);
if(j < l || r < i)return;
if(i <= l && r <= j){
if(t == 0)lzmn[node] = x;
else lzmx[node] = x;
refresh(node,l,r);
return;
}
int mid = (l+r)/2 , e = node*2,d = node*2+1;
update(e,l,mid,i,j,t,x); update(d,mid+1,r,i,j,t,x);
mx[0][node] = max(mx[0][e],mx[0][d]); mn[0][node] = min(mn[0][e],mn[0][d]);
}
int queryMN(int node, int l, int r, int i, int j, int k){
if(k == 0)refresh(node,l,r);
if(j < l || r < i)return MAXN;
if(i <= l && r <= j)return mn[k][node];
int mid = (l+r)/2, e = node*2, d = node*2+1;
return min(queryMN(e,l,mid,i,j,k), queryMN(d,mid+1,r,i,j,k));
}
int queryMX(int node, int l, int r, int i, int j, int k){
if(k == 0)refresh(node,l,r);
if(j < l || r < i)return 0;
if(i <= l && r <= j)return mx[k][node];
int mid = (l+r)/2, e = node*2, d = node*2+1;
return max(queryMX(e,l,mid,i,j,k), queryMX(d,mid+1,r,i,j,k));
}
void updateP(int node, int l, int r, int i, int k, int lx, int rx){
if(r < i || i < l)return;
if(l == r){
mn[k][node] = lx; mx[k][node] = rx;
return;
}
int mid = (l+r)/2, e = node*2, d = node*2+1;
updateP(e,l,mid,i,k,lx,rx); updateP(d,mid+1,r,i,k,lx,rx);
mx[k][node] = max(mx[k][e],mx[k][d]); mn[k][node] = min(mn[k][e], mn[k][d]);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,k,m; cin>>n>>k>>m;
build(1,1,n);
for(int i = 1; i <= m; i++){
int a,b; cin>>a>>b;
if(b > a) update(1,1,n, a, min(a+k-1,b), 1, b);
else update(1,1,n, max(a-k+1,b), a, 0, b);
}
for(int k = 1; k <= B; k++){
for(int i = 1; i <= n; i++){
int ini = queryMN(1,1,n, i,i, k-1);
int fim = queryMX(1,1,n, i,i, k-1);
int l = queryMN(1,1,n, ini, fim, k-1);
int r = queryMX(1,1,n, ini, fim, k-1);
updateP(1,1,n, i,k, l,r);
}
}
int q; cin>>q;
while(q--){
int s,t; cin>>s>>t;
int ans = 0, l = s, r = s;
for(int k = B; k >= 0; k--){
int ll = queryMN(1,1,n, l, r, k);
int rr = queryMX(1,1,n, l, r, k);
if(t < ll || rr < t){l = ll; r = rr; ans += (1<<k);}
}
int ll = queryMN(1,1,n, l, r, 0);
int rr = queryMX(1,1,n, l, r, 0);
if(t < ll || rr < t)cout<<"-1\n";
else cout<<ans+1<<"\n";
}
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |