#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int K;
int m;
int Q;
vector<pair<int,int>>rts[100005];
int rmq[19][19][100005];
int jmp[19][100005];
vector<pair<int,int>>rrts[100005];
int rrmq[19][19][100005];
int rjmp[19][100005];
void build(int id){
for(int i=1;i<=n;i++){
rmq[id][0][i]=jmp[id][i];
rrmq[id][0][i]=rjmp[id][i];
}
for(int i=1;i<=18;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
rmq[id][i][j]=max(rmq[id][i-1][j],rmq[id][i-1][j+(1<<(i-1))]);
rrmq[id][i][j]=min(rrmq[id][i-1][j],rrmq[id][i-1][j+(1<<(i-1))]);
}
}
}
int qmx(int id,int l,int r){
int len=r-l+1;
int lg=__lg(len);
return max(rmq[id][lg][l],rmq[id][lg][r-(1<<lg)+1]);
}
int qmn(int id,int l,int r){
int len=r-l+1;
int lg=__lg(len);
return min(rrmq[id][lg][l],rrmq[id][lg][r-(1<<lg)+1]);
}
signed main(){
cin>>n>>K;
cin>>m;
for(int i=1;i<=m;i++){
int a;int b;
cin>>a>>b;
if(a<b){
rts[a].push_back({min(b,a+K-1),b});
}
else{
rrts[a].push_back({max(b,a-K+1),b});
}
}
multiset<int>mst;
multiset<pair<int,int>>mst2;
for(int i=1;i<=n;i++){
for(int j=0;j<rts[i].size();j++){
mst.insert(rts[i][j].second);
mst2.insert({rts[i][j].first,rts[i][j].second});
}
while(mst2.size()&&(*mst2.begin()).first<i){
mst.erase(mst.find((*mst2.begin()).second));
mst2.erase(mst2.begin());
}
jmp[0][i]=i;
if(mst.size()){
jmp[0][i]=*mst.rbegin();
}
}
mst.clear();
mst2.clear();
for(int i=n;i>=1;i--){
for(int j=0;j<rrts[i].size();j++){
mst.insert(rrts[i][j].second);
mst2.insert({rrts[i][j].first,rrts[i][j].second});
}
while(mst2.size()&&((*mst2.rbegin()).first)>i){
mst.erase(mst.find((*mst2.rbegin()).second));
mst2.erase(prev(mst2.end()));
}
rjmp[0][i]=i;
if(mst.size()){
rjmp[0][i]=*mst.begin();
}
}
/*
for(int i=1;i<=n;i++){
cout<<rjmp[0][i]<<" ";
}cout<<endl;*/
//cout<<"hehe";
for(int i=1;i<=18;i++){
build(i-1);
for(int j=1;j<=n;j++){
jmp[i][j]=qmx(i-1,rjmp[i-1][j],jmp[i-1][j]);
rjmp[i][j]=qmn(i-1,rjmp[i-1][j],jmp[i-1][j]);
}
// cout<<i<<endl;
}
cin>>Q;
while(Q--){
int st;int en;
cin>>st>>en;
if(st<en){
int nwl=st;
int nwr=st;
int ans=0;
for(int i=17;i>=0;i--){
int nxtr=qmx(i,nwl,nwr);
if(nxtr<en){
nwl=qmn(i,nwl,nwr);
nwr=nxtr;
ans+=(1<<i);
}
}
// cout<<nw<<" "<<qmx(0,st,nw)<<" "<<jmp[0][nw]<<endl;
if(qmx(0,nwl,nwr)<en){
cout<<-1<<endl;
}else{
cout<<ans+1<<endl;
}
continue;
}
int nwl=st;
int nwr=st;
int ans=0;
for(int i=17;i>=0;i--){
int nxtl=qmn(i,nwl,nwr);
if(nxtl>en){
nwr=qmx(i,nwl,nwr);
nwl=nxtl;
ans+=(1<<i);
}
}
// cout<<nw<<" "<<qmx(0,st,nw)<<" "<<jmp[0][nw]<<endl;
if(qmn(0,nwl,nwr)>en){
cout<<-1<<endl;
}else{
cout<<ans+1<<endl;
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:58:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j=0;j<rts[i].size();j++){
| ~^~~~~~~~~~~~~~
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=0;j<rrts[i].size();j++){
| ~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7764 KB |
Output is correct |
2 |
Correct |
6 ms |
7712 KB |
Output is correct |
3 |
Correct |
5 ms |
7764 KB |
Output is correct |
4 |
Correct |
6 ms |
7720 KB |
Output is correct |
5 |
Correct |
5 ms |
7764 KB |
Output is correct |
6 |
Correct |
5 ms |
7764 KB |
Output is correct |
7 |
Correct |
5 ms |
7708 KB |
Output is correct |
8 |
Correct |
4 ms |
7764 KB |
Output is correct |
9 |
Correct |
5 ms |
7764 KB |
Output is correct |
10 |
Correct |
3 ms |
5588 KB |
Output is correct |
11 |
Correct |
5 ms |
7764 KB |
Output is correct |
12 |
Correct |
5 ms |
7764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7764 KB |
Output is correct |
2 |
Correct |
6 ms |
7712 KB |
Output is correct |
3 |
Correct |
5 ms |
7764 KB |
Output is correct |
4 |
Correct |
6 ms |
7720 KB |
Output is correct |
5 |
Correct |
5 ms |
7764 KB |
Output is correct |
6 |
Correct |
5 ms |
7764 KB |
Output is correct |
7 |
Correct |
5 ms |
7708 KB |
Output is correct |
8 |
Correct |
4 ms |
7764 KB |
Output is correct |
9 |
Correct |
5 ms |
7764 KB |
Output is correct |
10 |
Correct |
3 ms |
5588 KB |
Output is correct |
11 |
Correct |
5 ms |
7764 KB |
Output is correct |
12 |
Correct |
5 ms |
7764 KB |
Output is correct |
13 |
Correct |
12 ms |
13736 KB |
Output is correct |
14 |
Correct |
13 ms |
13780 KB |
Output is correct |
15 |
Correct |
8 ms |
13732 KB |
Output is correct |
16 |
Correct |
12 ms |
13736 KB |
Output is correct |
17 |
Correct |
14 ms |
13808 KB |
Output is correct |
18 |
Correct |
12 ms |
13868 KB |
Output is correct |
19 |
Correct |
12 ms |
13480 KB |
Output is correct |
20 |
Correct |
13 ms |
13732 KB |
Output is correct |
21 |
Correct |
9 ms |
13780 KB |
Output is correct |
22 |
Correct |
12 ms |
13732 KB |
Output is correct |
23 |
Correct |
13 ms |
13780 KB |
Output is correct |
24 |
Correct |
12 ms |
13740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
480776 KB |
Output is correct |
2 |
Correct |
260 ms |
481608 KB |
Output is correct |
3 |
Correct |
287 ms |
482556 KB |
Output is correct |
4 |
Correct |
271 ms |
481380 KB |
Output is correct |
5 |
Correct |
468 ms |
488500 KB |
Output is correct |
6 |
Correct |
362 ms |
486832 KB |
Output is correct |
7 |
Correct |
442 ms |
497484 KB |
Output is correct |
8 |
Correct |
338 ms |
481108 KB |
Output is correct |
9 |
Correct |
324 ms |
485020 KB |
Output is correct |
10 |
Correct |
384 ms |
485968 KB |
Output is correct |
11 |
Correct |
379 ms |
485880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
484088 KB |
Output is correct |
2 |
Correct |
530 ms |
486860 KB |
Output is correct |
3 |
Correct |
450 ms |
482112 KB |
Output is correct |
4 |
Correct |
511 ms |
496076 KB |
Output is correct |
5 |
Correct |
551 ms |
485700 KB |
Output is correct |
6 |
Correct |
655 ms |
489368 KB |
Output is correct |
7 |
Correct |
485 ms |
484024 KB |
Output is correct |
8 |
Correct |
518 ms |
484144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
654 ms |
488916 KB |
Output is correct |
2 |
Correct |
458 ms |
481640 KB |
Output is correct |
3 |
Correct |
420 ms |
480288 KB |
Output is correct |
4 |
Correct |
384 ms |
479172 KB |
Output is correct |
5 |
Correct |
364 ms |
478600 KB |
Output is correct |
6 |
Correct |
343 ms |
478512 KB |
Output is correct |
7 |
Correct |
416 ms |
492492 KB |
Output is correct |
8 |
Correct |
5 ms |
7764 KB |
Output is correct |
9 |
Correct |
12 ms |
13780 KB |
Output is correct |
10 |
Correct |
507 ms |
491088 KB |
Output is correct |
11 |
Correct |
587 ms |
494484 KB |
Output is correct |
12 |
Correct |
584 ms |
486376 KB |
Output is correct |
13 |
Correct |
638 ms |
494340 KB |
Output is correct |
14 |
Correct |
5 ms |
7764 KB |
Output is correct |
15 |
Correct |
14 ms |
13652 KB |
Output is correct |
16 |
Correct |
385 ms |
483556 KB |
Output is correct |
17 |
Correct |
527 ms |
483860 KB |
Output is correct |
18 |
Correct |
513 ms |
483800 KB |
Output is correct |
19 |
Correct |
496 ms |
483788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7764 KB |
Output is correct |
2 |
Correct |
6 ms |
7712 KB |
Output is correct |
3 |
Correct |
5 ms |
7764 KB |
Output is correct |
4 |
Correct |
6 ms |
7720 KB |
Output is correct |
5 |
Correct |
5 ms |
7764 KB |
Output is correct |
6 |
Correct |
5 ms |
7764 KB |
Output is correct |
7 |
Correct |
5 ms |
7708 KB |
Output is correct |
8 |
Correct |
4 ms |
7764 KB |
Output is correct |
9 |
Correct |
5 ms |
7764 KB |
Output is correct |
10 |
Correct |
3 ms |
5588 KB |
Output is correct |
11 |
Correct |
5 ms |
7764 KB |
Output is correct |
12 |
Correct |
5 ms |
7764 KB |
Output is correct |
13 |
Correct |
12 ms |
13736 KB |
Output is correct |
14 |
Correct |
13 ms |
13780 KB |
Output is correct |
15 |
Correct |
8 ms |
13732 KB |
Output is correct |
16 |
Correct |
12 ms |
13736 KB |
Output is correct |
17 |
Correct |
14 ms |
13808 KB |
Output is correct |
18 |
Correct |
12 ms |
13868 KB |
Output is correct |
19 |
Correct |
12 ms |
13480 KB |
Output is correct |
20 |
Correct |
13 ms |
13732 KB |
Output is correct |
21 |
Correct |
9 ms |
13780 KB |
Output is correct |
22 |
Correct |
12 ms |
13732 KB |
Output is correct |
23 |
Correct |
13 ms |
13780 KB |
Output is correct |
24 |
Correct |
12 ms |
13740 KB |
Output is correct |
25 |
Correct |
277 ms |
480776 KB |
Output is correct |
26 |
Correct |
260 ms |
481608 KB |
Output is correct |
27 |
Correct |
287 ms |
482556 KB |
Output is correct |
28 |
Correct |
271 ms |
481380 KB |
Output is correct |
29 |
Correct |
468 ms |
488500 KB |
Output is correct |
30 |
Correct |
362 ms |
486832 KB |
Output is correct |
31 |
Correct |
442 ms |
497484 KB |
Output is correct |
32 |
Correct |
338 ms |
481108 KB |
Output is correct |
33 |
Correct |
324 ms |
485020 KB |
Output is correct |
34 |
Correct |
384 ms |
485968 KB |
Output is correct |
35 |
Correct |
379 ms |
485880 KB |
Output is correct |
36 |
Correct |
407 ms |
484088 KB |
Output is correct |
37 |
Correct |
530 ms |
486860 KB |
Output is correct |
38 |
Correct |
450 ms |
482112 KB |
Output is correct |
39 |
Correct |
511 ms |
496076 KB |
Output is correct |
40 |
Correct |
551 ms |
485700 KB |
Output is correct |
41 |
Correct |
655 ms |
489368 KB |
Output is correct |
42 |
Correct |
485 ms |
484024 KB |
Output is correct |
43 |
Correct |
518 ms |
484144 KB |
Output is correct |
44 |
Correct |
654 ms |
488916 KB |
Output is correct |
45 |
Correct |
458 ms |
481640 KB |
Output is correct |
46 |
Correct |
420 ms |
480288 KB |
Output is correct |
47 |
Correct |
384 ms |
479172 KB |
Output is correct |
48 |
Correct |
364 ms |
478600 KB |
Output is correct |
49 |
Correct |
343 ms |
478512 KB |
Output is correct |
50 |
Correct |
416 ms |
492492 KB |
Output is correct |
51 |
Correct |
5 ms |
7764 KB |
Output is correct |
52 |
Correct |
12 ms |
13780 KB |
Output is correct |
53 |
Correct |
507 ms |
491088 KB |
Output is correct |
54 |
Correct |
587 ms |
494484 KB |
Output is correct |
55 |
Correct |
584 ms |
486376 KB |
Output is correct |
56 |
Correct |
638 ms |
494340 KB |
Output is correct |
57 |
Correct |
5 ms |
7764 KB |
Output is correct |
58 |
Correct |
14 ms |
13652 KB |
Output is correct |
59 |
Correct |
385 ms |
483556 KB |
Output is correct |
60 |
Correct |
527 ms |
483860 KB |
Output is correct |
61 |
Correct |
513 ms |
483800 KB |
Output is correct |
62 |
Correct |
496 ms |
483788 KB |
Output is correct |
63 |
Correct |
449 ms |
482224 KB |
Output is correct |
64 |
Correct |
461 ms |
482920 KB |
Output is correct |
65 |
Correct |
452 ms |
482464 KB |
Output is correct |
66 |
Correct |
545 ms |
489292 KB |
Output is correct |
67 |
Correct |
531 ms |
487644 KB |
Output is correct |
68 |
Correct |
562 ms |
484104 KB |
Output is correct |
69 |
Correct |
583 ms |
491852 KB |
Output is correct |
70 |
Correct |
521 ms |
486860 KB |
Output is correct |
71 |
Correct |
557 ms |
486648 KB |
Output is correct |