//#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=21;
int lg[N];
vector<int>addR[N];
vector<int>addL[N];
int l[N],r[N];
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;
pair<int,int>up[Lg][N];
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();
for (int i=1;i<=n;i++){
up[0][i]={L.get(l[i],r[i]),R.get(l[i],r[i])};
}
for (int j=1;j<=Lg;j++){
for (int i=1;i<=n;i++){
///calc up[j][i]
vector<int>consider;
consider.push_back(up[j-1][up[j-1][i].first].first);
consider.push_back(up[j-1][up[j-1][i].first].second);
consider.push_back(up[j-1][up[j-1][i].second].first);
consider.push_back(up[j-1][up[j-1][i].second].second);
up[j][i]=up[j-1][i];
for (int x:consider){
if (l[x]<l[up[j][i].first]) up[j][i].first=x;
if (r[x]>r[up[j][i].second]) up[j][i].second=x;
}
}
}
int q;cin>>q;
for (int i=1;i<=q;i++){
int s,t;cin>>s>>t;
if (l[up[Lg-1][s].first]>t || r[up[Lg-1][s].second]<t){
cout<<-1<<'\n';
continue;
}
if (l[s]<=t && t<=r[s]){
cout<<1<<'\n';
continue;
}
int res=0;
int sL=s,sR=s;
for (int j=Lg-1;j>=0;j--){
int nwL=sL;
int nwR=sR;
vector<int>consider;
consider.push_back(up[j][sL].first);
consider.push_back(up[j][sL].second);
consider.push_back(up[j][sR].first);
consider.push_back(up[j][sR].second);
for (int x:consider){
if (l[x]<l[nwL]) nwL=x;
if (r[x]>r[nwR]) nwR=x;
}
if (l[nwL]>t || r[nwR]<t){
res+=(1<<j);
sL=nwL;
sR=nwR;
}
}
res+=2;
cout<<res<<'\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 |
7 ms |
10740 KB |
Output is correct |
2 |
Correct |
8 ms |
10768 KB |
Output is correct |
3 |
Correct |
7 ms |
10836 KB |
Output is correct |
4 |
Correct |
8 ms |
10836 KB |
Output is correct |
5 |
Correct |
7 ms |
10768 KB |
Output is correct |
6 |
Correct |
8 ms |
10764 KB |
Output is correct |
7 |
Correct |
8 ms |
10804 KB |
Output is correct |
8 |
Correct |
9 ms |
10852 KB |
Output is correct |
9 |
Correct |
7 ms |
10776 KB |
Output is correct |
10 |
Correct |
8 ms |
10580 KB |
Output is correct |
11 |
Correct |
7 ms |
10836 KB |
Output is correct |
12 |
Correct |
7 ms |
10836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10740 KB |
Output is correct |
2 |
Correct |
8 ms |
10768 KB |
Output is correct |
3 |
Correct |
7 ms |
10836 KB |
Output is correct |
4 |
Correct |
8 ms |
10836 KB |
Output is correct |
5 |
Correct |
7 ms |
10768 KB |
Output is correct |
6 |
Correct |
8 ms |
10764 KB |
Output is correct |
7 |
Correct |
8 ms |
10804 KB |
Output is correct |
8 |
Correct |
9 ms |
10852 KB |
Output is correct |
9 |
Correct |
7 ms |
10776 KB |
Output is correct |
10 |
Correct |
8 ms |
10580 KB |
Output is correct |
11 |
Correct |
7 ms |
10836 KB |
Output is correct |
12 |
Correct |
7 ms |
10836 KB |
Output is correct |
13 |
Correct |
16 ms |
11428 KB |
Output is correct |
14 |
Correct |
15 ms |
11344 KB |
Output is correct |
15 |
Correct |
11 ms |
11400 KB |
Output is correct |
16 |
Correct |
11 ms |
11348 KB |
Output is correct |
17 |
Correct |
13 ms |
11476 KB |
Output is correct |
18 |
Correct |
12 ms |
11420 KB |
Output is correct |
19 |
Correct |
13 ms |
11436 KB |
Output is correct |
20 |
Correct |
12 ms |
11420 KB |
Output is correct |
21 |
Correct |
11 ms |
11420 KB |
Output is correct |
22 |
Correct |
11 ms |
11396 KB |
Output is correct |
23 |
Correct |
14 ms |
11356 KB |
Output is correct |
24 |
Correct |
15 ms |
11444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
44832 KB |
Output is correct |
2 |
Correct |
235 ms |
44824 KB |
Output is correct |
3 |
Correct |
249 ms |
44988 KB |
Output is correct |
4 |
Correct |
229 ms |
44736 KB |
Output is correct |
5 |
Correct |
356 ms |
48656 KB |
Output is correct |
6 |
Correct |
332 ms |
48124 KB |
Output is correct |
7 |
Correct |
300 ms |
53824 KB |
Output is correct |
8 |
Correct |
245 ms |
46668 KB |
Output is correct |
9 |
Correct |
246 ms |
47052 KB |
Output is correct |
10 |
Correct |
310 ms |
47516 KB |
Output is correct |
11 |
Correct |
298 ms |
47464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
327 ms |
47880 KB |
Output is correct |
2 |
Correct |
343 ms |
51152 KB |
Output is correct |
3 |
Correct |
365 ms |
46508 KB |
Output is correct |
4 |
Correct |
316 ms |
55764 KB |
Output is correct |
5 |
Correct |
333 ms |
51996 KB |
Output is correct |
6 |
Correct |
327 ms |
52172 KB |
Output is correct |
7 |
Correct |
386 ms |
50236 KB |
Output is correct |
8 |
Correct |
414 ms |
50124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
48696 KB |
Output is correct |
2 |
Correct |
400 ms |
45628 KB |
Output is correct |
3 |
Correct |
443 ms |
44376 KB |
Output is correct |
4 |
Correct |
346 ms |
43024 KB |
Output is correct |
5 |
Correct |
365 ms |
42612 KB |
Output is correct |
6 |
Correct |
290 ms |
42180 KB |
Output is correct |
7 |
Correct |
243 ms |
51480 KB |
Output is correct |
8 |
Correct |
6 ms |
10852 KB |
Output is correct |
9 |
Correct |
18 ms |
11428 KB |
Output is correct |
10 |
Correct |
358 ms |
51076 KB |
Output is correct |
11 |
Correct |
336 ms |
53156 KB |
Output is correct |
12 |
Correct |
369 ms |
51060 KB |
Output is correct |
13 |
Correct |
345 ms |
53136 KB |
Output is correct |
14 |
Correct |
7 ms |
10836 KB |
Output is correct |
15 |
Correct |
15 ms |
11348 KB |
Output is correct |
16 |
Correct |
252 ms |
47912 KB |
Output is correct |
17 |
Correct |
461 ms |
48796 KB |
Output is correct |
18 |
Correct |
408 ms |
48616 KB |
Output is correct |
19 |
Correct |
500 ms |
48736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10740 KB |
Output is correct |
2 |
Correct |
8 ms |
10768 KB |
Output is correct |
3 |
Correct |
7 ms |
10836 KB |
Output is correct |
4 |
Correct |
8 ms |
10836 KB |
Output is correct |
5 |
Correct |
7 ms |
10768 KB |
Output is correct |
6 |
Correct |
8 ms |
10764 KB |
Output is correct |
7 |
Correct |
8 ms |
10804 KB |
Output is correct |
8 |
Correct |
9 ms |
10852 KB |
Output is correct |
9 |
Correct |
7 ms |
10776 KB |
Output is correct |
10 |
Correct |
8 ms |
10580 KB |
Output is correct |
11 |
Correct |
7 ms |
10836 KB |
Output is correct |
12 |
Correct |
7 ms |
10836 KB |
Output is correct |
13 |
Correct |
16 ms |
11428 KB |
Output is correct |
14 |
Correct |
15 ms |
11344 KB |
Output is correct |
15 |
Correct |
11 ms |
11400 KB |
Output is correct |
16 |
Correct |
11 ms |
11348 KB |
Output is correct |
17 |
Correct |
13 ms |
11476 KB |
Output is correct |
18 |
Correct |
12 ms |
11420 KB |
Output is correct |
19 |
Correct |
13 ms |
11436 KB |
Output is correct |
20 |
Correct |
12 ms |
11420 KB |
Output is correct |
21 |
Correct |
11 ms |
11420 KB |
Output is correct |
22 |
Correct |
11 ms |
11396 KB |
Output is correct |
23 |
Correct |
14 ms |
11356 KB |
Output is correct |
24 |
Correct |
15 ms |
11444 KB |
Output is correct |
25 |
Correct |
238 ms |
44832 KB |
Output is correct |
26 |
Correct |
235 ms |
44824 KB |
Output is correct |
27 |
Correct |
249 ms |
44988 KB |
Output is correct |
28 |
Correct |
229 ms |
44736 KB |
Output is correct |
29 |
Correct |
356 ms |
48656 KB |
Output is correct |
30 |
Correct |
332 ms |
48124 KB |
Output is correct |
31 |
Correct |
300 ms |
53824 KB |
Output is correct |
32 |
Correct |
245 ms |
46668 KB |
Output is correct |
33 |
Correct |
246 ms |
47052 KB |
Output is correct |
34 |
Correct |
310 ms |
47516 KB |
Output is correct |
35 |
Correct |
298 ms |
47464 KB |
Output is correct |
36 |
Correct |
327 ms |
47880 KB |
Output is correct |
37 |
Correct |
343 ms |
51152 KB |
Output is correct |
38 |
Correct |
365 ms |
46508 KB |
Output is correct |
39 |
Correct |
316 ms |
55764 KB |
Output is correct |
40 |
Correct |
333 ms |
51996 KB |
Output is correct |
41 |
Correct |
327 ms |
52172 KB |
Output is correct |
42 |
Correct |
386 ms |
50236 KB |
Output is correct |
43 |
Correct |
414 ms |
50124 KB |
Output is correct |
44 |
Correct |
345 ms |
48696 KB |
Output is correct |
45 |
Correct |
400 ms |
45628 KB |
Output is correct |
46 |
Correct |
443 ms |
44376 KB |
Output is correct |
47 |
Correct |
346 ms |
43024 KB |
Output is correct |
48 |
Correct |
365 ms |
42612 KB |
Output is correct |
49 |
Correct |
290 ms |
42180 KB |
Output is correct |
50 |
Correct |
243 ms |
51480 KB |
Output is correct |
51 |
Correct |
6 ms |
10852 KB |
Output is correct |
52 |
Correct |
18 ms |
11428 KB |
Output is correct |
53 |
Correct |
358 ms |
51076 KB |
Output is correct |
54 |
Correct |
336 ms |
53156 KB |
Output is correct |
55 |
Correct |
369 ms |
51060 KB |
Output is correct |
56 |
Correct |
345 ms |
53136 KB |
Output is correct |
57 |
Correct |
7 ms |
10836 KB |
Output is correct |
58 |
Correct |
15 ms |
11348 KB |
Output is correct |
59 |
Correct |
252 ms |
47912 KB |
Output is correct |
60 |
Correct |
461 ms |
48796 KB |
Output is correct |
61 |
Correct |
408 ms |
48616 KB |
Output is correct |
62 |
Correct |
500 ms |
48736 KB |
Output is correct |
63 |
Correct |
386 ms |
45832 KB |
Output is correct |
64 |
Correct |
439 ms |
46316 KB |
Output is correct |
65 |
Correct |
361 ms |
46024 KB |
Output is correct |
66 |
Correct |
345 ms |
51148 KB |
Output is correct |
67 |
Correct |
436 ms |
50816 KB |
Output is correct |
68 |
Correct |
356 ms |
49828 KB |
Output is correct |
69 |
Correct |
364 ms |
52092 KB |
Output is correct |
70 |
Correct |
347 ms |
50056 KB |
Output is correct |
71 |
Correct |
480 ms |
50092 KB |
Output is correct |