#include<bits/stdc++.h>
using namespace std;
int zl,zr;
int MDE;
int a,b,c,d,e,i,j,ii,zx,xc,K,tes,t,segMN[18][400009],segMN2[18][400009],segMX[18][400009],segMX2[18][400009],l,r,za,lf[18][400009],rg[18][400009],L,R,pas,ANS;
int JJ;
/*void pushdown(int q, int w, int rr){
if(q!=w){
segMX2[JJ][rr*2]=max(segMX2[JJ][rr*2],segMX2[JJ][rr]);
segMX2[JJ][rr*2+1]=max(segMX2[JJ][rr*2+1],segMX2[JJ][rr]);
segMN2[JJ][rr*2]=min(segMN2[JJ][rr*2],segMN2[JJ][rr]);
segMN2[JJ][rr*2+1]=min(segMN2[JJ][rr*2+1],segMN2[JJ][rr]);
}
segMX[JJ][rr]=max(segMX[JJ][rr],segMX2[JJ][rr]);
segMX2[JJ][rr]=0;
segMN[JJ][rr]=min(segMN[JJ][rr],segMN2[JJ][rr]);
segMN2[JJ][rr]=a+2;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
segMX2[JJ][rr]=zr;
segMN2[JJ][rr]=zl;
pushdown(q,w,rr);
return;
}
upd(q,((q+w)>>1),rr*2);
upd(((q+w)>>1)+1,w,rr*2+1);
segMX[JJ][rr]=max(segMX[JJ][rr*2],segMX[JJ][rr*2+1]);
segMN[JJ][rr]=min(segMN[JJ][rr*2],segMN[JJ][rr*2+1]);
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
zr=max(zr,segMX[JJ][rr]);
zl=min(zl,segMN[JJ][rr]);
return;
}
read(q,((q+w)>>1),rr*2);
read(((q+w)>>1)+1,w,rr*2+1);
}*/
void read(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
zr=max(zr,segMX[JJ][rr]);
zl=min(zl,segMN[JJ][rr]);
return;
}
read(q,((q+w)>>1),rr*2);
read(((q+w)>>1)+1,w,rr*2+1);
}
void UPD(int q, int zl, int zr){
q=za+q-1;
segMN[JJ][q]=zl;segMX[JJ][q]=zr;
q/=2;
while(q){
segMX[JJ][q]=max(segMX[JJ][q*2],segMX[JJ][q*2+1]);
segMN[JJ][q]=min(segMN[JJ][q*2],segMN[JJ][q*2+1]);
q>>=1;
}
}
vector <int> MN[100009],MX[100009];
multiset <int> sMN,sMX;
multiset <int>::iterator it;
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>K;
cin>>b;
za=1;
while(za<a) za*=2;
for(j=0; j<=17; j++){
for(i=0; i<=za*2; i++){
segMN[j][i]=a+2;
segMX[j][i]=0;
segMN2[j][i]=a+2;
segMX2[j][i]=0;
}
}
for(ii=1; ii<=b; ii++){
cin>>c>>d;
if(c<=d){
l=c;r=min(d,c+K-1);JJ=0;
zr=d;zl=a+2;
//upd(1,za,1);
MX[l].push_back(zr);
MX[r+1].push_back(-zr);
}else{
swap(c,d);
l=max(d-K+1,c);r=d;JJ=0;
zl=c;zr=0;
//upd(1,za,1);
MN[l].push_back(zl);
MN[r+1].push_back(-zl);
}
}
for(i=1; i<=a; i++){
for(auto x:MN[i]){
if(x>=0){
sMN.insert(x);
}else{
sMN.erase(sMN.find(-x));
}
}
for(auto x:MX[i]){
if(x>=0){
sMX.insert(x);
}else{
sMX.erase(sMX.find(-x));
}
}
lf[0][i]=rg[0][i]=i;
if(sMN.size()){
it=sMN.begin();
lf[0][i]=(*it);
}
if(sMX.size()){
it=sMX.end();
it--;
rg[0][i]=(*it);
}
}
for(i=1; i<=a; i++){
JJ=0;
l=i;r=i;
zl=lf[0][i];zr=rg[0][i];
//cout<<i<<" "<<zl<<" "<<zr<<"\n";
UPD(i,zl,zr);
}
/*for(i=1; i<=a; i++){
//lf[0][i]=rg[0][i]=i;
l=i;r=i;zl=a+2;zr=0;JJ=0;
read(1,za,1);
c=min(zl,i);
d=max(zr,i);
lf[0][i]=c;
rg[0][i]=d;
}*/
for(j=0; j<16; j++){
for(i=1; i<=a; i++){
l=lf[j][i];r=rg[j][i];JJ=j;
zl=a+2;zr=0;
read(1,za,1);
c=min(zl,lf[j][i]);
d=max(zr,rg[j][i]);
/*zx=c;xc=d;
l=c;r=d;z=a+2;JJ=j;
readMN(1,za,1);
zx=min(zx,z);
l=c;r=d;z=0;JJ=j;
readMX(1,za,1);
xc=max(xc,z);*/
//c=zx;d=xc;
lf[j+1][i]=c;rg[j+1][i]=d;
if(c>=lf[j][i]&&d<=rg[j][i]){
;
}else{
MDE=max(MDE,j+1);
}
l=i;r=i;JJ=j+1;
zr=d;zl=c;
//upd(1,za,1);
UPD(i,zl,zr);
}
}
cin>>tes;
for(t=1; t<=tes; t++){
cin>>c>>d;
L=c;R=c;
ANS=b+1;pas=0;
for(j=MDE; j>=0; j--){
zx=L;xc=R;
l=L;r=R;JJ=j;
zr=0;zl=a+2;
read(1,za,1);
xc=max(xc,zr);
zx=min(zx,zl);
//cout<<j<<": "<<L<<" "<<R<<" "<<zx<<" "<<xc<<"\n";
if(zx<=d&&d<=xc){
ANS=min(ANS,pas+(1<<j));
}else{
pas+=(1<<j);
L=min(L,zx);
R=max(R,xc);
}
}
if(ANS==b+1) cout<<"-1\n"; else cout<<ANS<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6100 KB |
Output is correct |
2 |
Correct |
3 ms |
6100 KB |
Output is correct |
3 |
Correct |
3 ms |
6100 KB |
Output is correct |
4 |
Correct |
3 ms |
6100 KB |
Output is correct |
5 |
Correct |
4 ms |
6184 KB |
Output is correct |
6 |
Correct |
3 ms |
6100 KB |
Output is correct |
7 |
Correct |
3 ms |
6100 KB |
Output is correct |
8 |
Correct |
3 ms |
6100 KB |
Output is correct |
9 |
Correct |
3 ms |
6100 KB |
Output is correct |
10 |
Correct |
2 ms |
5716 KB |
Output is correct |
11 |
Correct |
3 ms |
6100 KB |
Output is correct |
12 |
Correct |
3 ms |
6100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6100 KB |
Output is correct |
2 |
Correct |
3 ms |
6100 KB |
Output is correct |
3 |
Correct |
3 ms |
6100 KB |
Output is correct |
4 |
Correct |
3 ms |
6100 KB |
Output is correct |
5 |
Correct |
4 ms |
6184 KB |
Output is correct |
6 |
Correct |
3 ms |
6100 KB |
Output is correct |
7 |
Correct |
3 ms |
6100 KB |
Output is correct |
8 |
Correct |
3 ms |
6100 KB |
Output is correct |
9 |
Correct |
3 ms |
6100 KB |
Output is correct |
10 |
Correct |
2 ms |
5716 KB |
Output is correct |
11 |
Correct |
3 ms |
6100 KB |
Output is correct |
12 |
Correct |
3 ms |
6100 KB |
Output is correct |
13 |
Correct |
10 ms |
7252 KB |
Output is correct |
14 |
Correct |
9 ms |
7252 KB |
Output is correct |
15 |
Correct |
7 ms |
7252 KB |
Output is correct |
16 |
Correct |
7 ms |
7252 KB |
Output is correct |
17 |
Correct |
10 ms |
7252 KB |
Output is correct |
18 |
Correct |
7 ms |
7380 KB |
Output is correct |
19 |
Correct |
8 ms |
7252 KB |
Output is correct |
20 |
Correct |
7 ms |
7252 KB |
Output is correct |
21 |
Correct |
6 ms |
7252 KB |
Output is correct |
22 |
Correct |
8 ms |
7252 KB |
Output is correct |
23 |
Correct |
8 ms |
7216 KB |
Output is correct |
24 |
Correct |
9 ms |
7252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
400 ms |
96076 KB |
Output is correct |
2 |
Correct |
383 ms |
95908 KB |
Output is correct |
3 |
Correct |
425 ms |
96076 KB |
Output is correct |
4 |
Correct |
372 ms |
95896 KB |
Output is correct |
5 |
Correct |
380 ms |
100832 KB |
Output is correct |
6 |
Correct |
410 ms |
99196 KB |
Output is correct |
7 |
Correct |
286 ms |
104708 KB |
Output is correct |
8 |
Correct |
270 ms |
99148 KB |
Output is correct |
9 |
Correct |
266 ms |
99628 KB |
Output is correct |
10 |
Correct |
402 ms |
98956 KB |
Output is correct |
11 |
Correct |
379 ms |
99104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
444 ms |
100520 KB |
Output is correct |
2 |
Correct |
439 ms |
103696 KB |
Output is correct |
3 |
Correct |
620 ms |
100880 KB |
Output is correct |
4 |
Correct |
293 ms |
107148 KB |
Output is correct |
5 |
Correct |
363 ms |
105736 KB |
Output is correct |
6 |
Correct |
357 ms |
105976 KB |
Output is correct |
7 |
Correct |
491 ms |
101280 KB |
Output is correct |
8 |
Correct |
521 ms |
101420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
508 ms |
99948 KB |
Output is correct |
2 |
Correct |
684 ms |
97332 KB |
Output is correct |
3 |
Correct |
596 ms |
95700 KB |
Output is correct |
4 |
Correct |
590 ms |
94412 KB |
Output is correct |
5 |
Correct |
441 ms |
93904 KB |
Output is correct |
6 |
Correct |
500 ms |
93432 KB |
Output is correct |
7 |
Correct |
400 ms |
102864 KB |
Output is correct |
8 |
Correct |
4 ms |
6104 KB |
Output is correct |
9 |
Correct |
9 ms |
7252 KB |
Output is correct |
10 |
Correct |
468 ms |
102452 KB |
Output is correct |
11 |
Correct |
479 ms |
104524 KB |
Output is correct |
12 |
Correct |
508 ms |
102604 KB |
Output is correct |
13 |
Correct |
478 ms |
104660 KB |
Output is correct |
14 |
Correct |
3 ms |
6100 KB |
Output is correct |
15 |
Correct |
10 ms |
7220 KB |
Output is correct |
16 |
Correct |
414 ms |
99220 KB |
Output is correct |
17 |
Correct |
640 ms |
100004 KB |
Output is correct |
18 |
Correct |
592 ms |
99948 KB |
Output is correct |
19 |
Correct |
554 ms |
99972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6100 KB |
Output is correct |
2 |
Correct |
3 ms |
6100 KB |
Output is correct |
3 |
Correct |
3 ms |
6100 KB |
Output is correct |
4 |
Correct |
3 ms |
6100 KB |
Output is correct |
5 |
Correct |
4 ms |
6184 KB |
Output is correct |
6 |
Correct |
3 ms |
6100 KB |
Output is correct |
7 |
Correct |
3 ms |
6100 KB |
Output is correct |
8 |
Correct |
3 ms |
6100 KB |
Output is correct |
9 |
Correct |
3 ms |
6100 KB |
Output is correct |
10 |
Correct |
2 ms |
5716 KB |
Output is correct |
11 |
Correct |
3 ms |
6100 KB |
Output is correct |
12 |
Correct |
3 ms |
6100 KB |
Output is correct |
13 |
Correct |
10 ms |
7252 KB |
Output is correct |
14 |
Correct |
9 ms |
7252 KB |
Output is correct |
15 |
Correct |
7 ms |
7252 KB |
Output is correct |
16 |
Correct |
7 ms |
7252 KB |
Output is correct |
17 |
Correct |
10 ms |
7252 KB |
Output is correct |
18 |
Correct |
7 ms |
7380 KB |
Output is correct |
19 |
Correct |
8 ms |
7252 KB |
Output is correct |
20 |
Correct |
7 ms |
7252 KB |
Output is correct |
21 |
Correct |
6 ms |
7252 KB |
Output is correct |
22 |
Correct |
8 ms |
7252 KB |
Output is correct |
23 |
Correct |
8 ms |
7216 KB |
Output is correct |
24 |
Correct |
9 ms |
7252 KB |
Output is correct |
25 |
Correct |
400 ms |
96076 KB |
Output is correct |
26 |
Correct |
383 ms |
95908 KB |
Output is correct |
27 |
Correct |
425 ms |
96076 KB |
Output is correct |
28 |
Correct |
372 ms |
95896 KB |
Output is correct |
29 |
Correct |
380 ms |
100832 KB |
Output is correct |
30 |
Correct |
410 ms |
99196 KB |
Output is correct |
31 |
Correct |
286 ms |
104708 KB |
Output is correct |
32 |
Correct |
270 ms |
99148 KB |
Output is correct |
33 |
Correct |
266 ms |
99628 KB |
Output is correct |
34 |
Correct |
402 ms |
98956 KB |
Output is correct |
35 |
Correct |
379 ms |
99104 KB |
Output is correct |
36 |
Correct |
444 ms |
100520 KB |
Output is correct |
37 |
Correct |
439 ms |
103696 KB |
Output is correct |
38 |
Correct |
620 ms |
100880 KB |
Output is correct |
39 |
Correct |
293 ms |
107148 KB |
Output is correct |
40 |
Correct |
363 ms |
105736 KB |
Output is correct |
41 |
Correct |
357 ms |
105976 KB |
Output is correct |
42 |
Correct |
491 ms |
101280 KB |
Output is correct |
43 |
Correct |
521 ms |
101420 KB |
Output is correct |
44 |
Correct |
508 ms |
99948 KB |
Output is correct |
45 |
Correct |
684 ms |
97332 KB |
Output is correct |
46 |
Correct |
596 ms |
95700 KB |
Output is correct |
47 |
Correct |
590 ms |
94412 KB |
Output is correct |
48 |
Correct |
441 ms |
93904 KB |
Output is correct |
49 |
Correct |
500 ms |
93432 KB |
Output is correct |
50 |
Correct |
400 ms |
102864 KB |
Output is correct |
51 |
Correct |
4 ms |
6104 KB |
Output is correct |
52 |
Correct |
9 ms |
7252 KB |
Output is correct |
53 |
Correct |
468 ms |
102452 KB |
Output is correct |
54 |
Correct |
479 ms |
104524 KB |
Output is correct |
55 |
Correct |
508 ms |
102604 KB |
Output is correct |
56 |
Correct |
478 ms |
104660 KB |
Output is correct |
57 |
Correct |
3 ms |
6100 KB |
Output is correct |
58 |
Correct |
10 ms |
7220 KB |
Output is correct |
59 |
Correct |
414 ms |
99220 KB |
Output is correct |
60 |
Correct |
640 ms |
100004 KB |
Output is correct |
61 |
Correct |
592 ms |
99948 KB |
Output is correct |
62 |
Correct |
554 ms |
99972 KB |
Output is correct |
63 |
Correct |
583 ms |
97212 KB |
Output is correct |
64 |
Correct |
663 ms |
97636 KB |
Output is correct |
65 |
Correct |
618 ms |
97228 KB |
Output is correct |
66 |
Correct |
407 ms |
103708 KB |
Output is correct |
67 |
Correct |
581 ms |
102084 KB |
Output is correct |
68 |
Correct |
372 ms |
101368 KB |
Output is correct |
69 |
Correct |
357 ms |
105804 KB |
Output is correct |
70 |
Correct |
511 ms |
101308 KB |
Output is correct |
71 |
Correct |
619 ms |
101336 KB |
Output is correct |