//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
//#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll inf=1e18;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=200010;
const int Lg=20;
int lg[N];
vector<int>addR[N];
vector<int>addL[N];
int l[N],r[N];
pair<int,int>up[N][Lg];
struct SparseTable{
int mult;
int a[N];
int best[Lg][N];
int n;
void build(){
for (int i=1;i<=n;i++) a[i]*=mult;
for (int i=1;i<=n;i++) best[0][i]=i;
for (int j=1;j<Lg;j++){
for (int i=1;i<=n-(1<<j)+1;i++){
int x=best[j-1][i];
int y=best[j-1][i+(1<<(j-1))];
if (a[x]>a[y]) best[j][i]=x;
else best[j][i]=y;
}
}
}
int get(int l,int r){
int len=lg[r-l+1];
int x=best[len][l];
int y=best[len][r-(1<<len)+1];
// if (l+(1<<len)-1>n) exit(1);
if (a[x]>a[y]) return x;
return y;
}
};
SparseTable L;
SparseTable R;
void solve(){
int n,k,m;cin>>n>>k>>m;
for (int i=1;i<=m;i++){
int a,b;cin>>a>>b;
if (a<b){
int l=a;
int r=min(a+k-1,b-1);
addR[l].push_back(b);
addR[r+1].push_back(-b);
} else {
swap(a,b);
int r=b;
int l=max(a+1,b-k+1);
addL[r].push_back(a);
addL[l-1].push_back(-a);
}
}
multiset<int>st;
for (int i=1;i<=n;i++){
for (int x:addR[i]){
if (x<0) st.erase(st.find(-x));
else st.insert(x);
}
r[i]=i;
if (!st.empty()) r[i]=max(r[i],(*st.rbegin()));
}
st.clear();
for (int i=n;i>=1;i--){
for (int x:addL[i]){
if (x<0) st.erase(st.find(-x));
if (x>0) st.insert(x);
}
l[i]=i;
if (!st.empty()) l[i]=min(l[i],(*st.begin()));
}
L.mult=-1;
R.mult=1;
L.n=R.n=n;
for (int i=1;i<=n;i++){
// cout<<i<<" "<<l[i]<<" "<<r[i]<<'\n';
L.a[i]=l[i];
R.a[i]=r[i];
}
L.build();
R.build();
int q;cin>>q;
for (int i=1;i<=q;i++){
int s,t;cin>>s>>t;
int sL=s,sR=s;
int res=0;
while (t<sL || t>sR){
int nwL=l[L.get(sL,sR)];
int nwR=r[R.get(sL,sR)];
if (nwL==sL && nwR==sR) break;
// cout<<sL<<" "<<sR<<" "<<nwL<<" "<<nwR<<" "<<L.get(sL,sR)<<endl;
sL=nwL;
sR=nwR;
res++;
}
if (sL<=t && t<=sR) cout<<res<<'\n';
else cout<<-1<<'\n';
}
}
int32_t main() {
lg[1]=0;
for (int i=2;i<N;i++) lg[i]=lg[i/2]+1;
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt=1;
// cin>>tt;
while (tt--){
solve();
}
return 0;
}
/**
3
5 2 7 3 1 6 8 4
**/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10580 KB |
Output is correct |
2 |
Correct |
7 ms |
10580 KB |
Output is correct |
3 |
Correct |
6 ms |
10580 KB |
Output is correct |
4 |
Correct |
6 ms |
10580 KB |
Output is correct |
5 |
Correct |
7 ms |
10580 KB |
Output is correct |
6 |
Correct |
5 ms |
10648 KB |
Output is correct |
7 |
Correct |
6 ms |
10580 KB |
Output is correct |
8 |
Correct |
6 ms |
10636 KB |
Output is correct |
9 |
Correct |
6 ms |
10648 KB |
Output is correct |
10 |
Correct |
5 ms |
10452 KB |
Output is correct |
11 |
Correct |
7 ms |
10580 KB |
Output is correct |
12 |
Correct |
5 ms |
10580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10580 KB |
Output is correct |
2 |
Correct |
7 ms |
10580 KB |
Output is correct |
3 |
Correct |
6 ms |
10580 KB |
Output is correct |
4 |
Correct |
6 ms |
10580 KB |
Output is correct |
5 |
Correct |
7 ms |
10580 KB |
Output is correct |
6 |
Correct |
5 ms |
10648 KB |
Output is correct |
7 |
Correct |
6 ms |
10580 KB |
Output is correct |
8 |
Correct |
6 ms |
10636 KB |
Output is correct |
9 |
Correct |
6 ms |
10648 KB |
Output is correct |
10 |
Correct |
5 ms |
10452 KB |
Output is correct |
11 |
Correct |
7 ms |
10580 KB |
Output is correct |
12 |
Correct |
5 ms |
10580 KB |
Output is correct |
13 |
Correct |
24 ms |
10944 KB |
Output is correct |
14 |
Correct |
17 ms |
10904 KB |
Output is correct |
15 |
Correct |
6 ms |
10836 KB |
Output is correct |
16 |
Correct |
8 ms |
10964 KB |
Output is correct |
17 |
Correct |
10 ms |
10964 KB |
Output is correct |
18 |
Correct |
7 ms |
10948 KB |
Output is correct |
19 |
Correct |
7 ms |
10844 KB |
Output is correct |
20 |
Correct |
7 ms |
10964 KB |
Output is correct |
21 |
Correct |
6 ms |
10964 KB |
Output is correct |
22 |
Correct |
7 ms |
10912 KB |
Output is correct |
23 |
Correct |
7 ms |
10964 KB |
Output is correct |
24 |
Correct |
7 ms |
10964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
28468 KB |
Output is correct |
2 |
Correct |
41 ms |
28236 KB |
Output is correct |
3 |
Correct |
59 ms |
28868 KB |
Output is correct |
4 |
Correct |
40 ms |
28240 KB |
Output is correct |
5 |
Correct |
152 ms |
33476 KB |
Output is correct |
6 |
Correct |
141 ms |
32972 KB |
Output is correct |
7 |
Correct |
135 ms |
38248 KB |
Output is correct |
8 |
Correct |
86 ms |
30556 KB |
Output is correct |
9 |
Correct |
79 ms |
30756 KB |
Output is correct |
10 |
Correct |
132 ms |
32368 KB |
Output is correct |
11 |
Correct |
117 ms |
32380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2071 ms |
31716 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
188 ms |
34208 KB |
Output is correct |
2 |
Execution timed out |
2064 ms |
29192 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10580 KB |
Output is correct |
2 |
Correct |
7 ms |
10580 KB |
Output is correct |
3 |
Correct |
6 ms |
10580 KB |
Output is correct |
4 |
Correct |
6 ms |
10580 KB |
Output is correct |
5 |
Correct |
7 ms |
10580 KB |
Output is correct |
6 |
Correct |
5 ms |
10648 KB |
Output is correct |
7 |
Correct |
6 ms |
10580 KB |
Output is correct |
8 |
Correct |
6 ms |
10636 KB |
Output is correct |
9 |
Correct |
6 ms |
10648 KB |
Output is correct |
10 |
Correct |
5 ms |
10452 KB |
Output is correct |
11 |
Correct |
7 ms |
10580 KB |
Output is correct |
12 |
Correct |
5 ms |
10580 KB |
Output is correct |
13 |
Correct |
24 ms |
10944 KB |
Output is correct |
14 |
Correct |
17 ms |
10904 KB |
Output is correct |
15 |
Correct |
6 ms |
10836 KB |
Output is correct |
16 |
Correct |
8 ms |
10964 KB |
Output is correct |
17 |
Correct |
10 ms |
10964 KB |
Output is correct |
18 |
Correct |
7 ms |
10948 KB |
Output is correct |
19 |
Correct |
7 ms |
10844 KB |
Output is correct |
20 |
Correct |
7 ms |
10964 KB |
Output is correct |
21 |
Correct |
6 ms |
10964 KB |
Output is correct |
22 |
Correct |
7 ms |
10912 KB |
Output is correct |
23 |
Correct |
7 ms |
10964 KB |
Output is correct |
24 |
Correct |
7 ms |
10964 KB |
Output is correct |
25 |
Correct |
43 ms |
28468 KB |
Output is correct |
26 |
Correct |
41 ms |
28236 KB |
Output is correct |
27 |
Correct |
59 ms |
28868 KB |
Output is correct |
28 |
Correct |
40 ms |
28240 KB |
Output is correct |
29 |
Correct |
152 ms |
33476 KB |
Output is correct |
30 |
Correct |
141 ms |
32972 KB |
Output is correct |
31 |
Correct |
135 ms |
38248 KB |
Output is correct |
32 |
Correct |
86 ms |
30556 KB |
Output is correct |
33 |
Correct |
79 ms |
30756 KB |
Output is correct |
34 |
Correct |
132 ms |
32368 KB |
Output is correct |
35 |
Correct |
117 ms |
32380 KB |
Output is correct |
36 |
Execution timed out |
2071 ms |
31716 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |