#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sf scanf
#define pf printf
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
#define maxn 100005
#define INF 1023456789
struct node{
int s,e,m;pair<int,int> v;
node *l,*r;
node(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;v={0,0};
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void up(int x,ii nv){
if(s==x&&e==x){v=nv;return;}
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v={min(l->v.fi,r->v.fi),max(l->v.se,r->v.se)};
}
ii qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
ii pl=qry(x,m),pr=qry(m+1,y);
return {min(pl.fi,pr.fi),max(pl.se,pr.se)};
}
}*rt[20];
int n,k,m,q,mn[20][maxn],mx[20][maxn];
inline int getmn(int l,int r){
l=max(1,l),r=min(n,r);
int k=31-__builtin_clz(r-l+1);
return min(mn[k][l],mn[k][r-(1<<k)+1]);
}
inline int getmx(int l,int r){
l=max(1,l),r=min(n,r);
int k=31-__builtin_clz(r-l+1);
return max(mx[k][l],mx[k][r-(1<<k)+1]);
}
int main(){
sf("%d%d%d",&n,&k,&m);
for(int i=1;i<=n;++i)mn[0][i]=mx[0][i]=i;
for(int i=0;i<m;++i){
int a,b;sf("%d%d",&a,&b);
mx[0][a]=max(mx[0][a],b);
mn[0][a]=min(mn[0][a],b);
}
for(int k=1;k<20;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
mx[k][i]=max(mx[k-1][i],mx[k-1][i+(1<<(k-1))]);
mn[k][i]=min(mn[k-1][i],mn[k-1][i+(1<<(k-1))]);
}
}
rt[0]=new node(1,n);
//pf("0: ");
for(int i=1;i<=n;++i){
int l=min(i,getmn(i,i+k-1)),r=max(i,getmx(i-k+1,i));
rt[0]->up(i,{l,r});
//pf("(%d: %d %d) ",i,l,r);
}
//pf("\n");
for(int k=1;k<20;++k){
rt[k]=new node(1,n);
//pf("%d: ",k);
for(int i=1;i<=n;++i){
ii pr=rt[k-1]->qry(i,i);
rt[k]->up(i,rt[k-1]->qry(pr.fi,pr.se));
//pf("(%d: %d %d) ",i,rt[k]->qry(i,i).fi,rt[k]->qry(i,i).se);
}
//pf("\n");
}
sf("%d",&q);
for(int i=0;i<q;++i){
int s,t;sf("%d%d",&s,&t);
ii pr=rt[19]->qry(s,s);
if(t<pr.fi||pr.se<t){
pf("-1\n");
continue;
}
int l=s,r=s,ans=0;
for(int k=19;k>=0;--k){
ii pr=rt[k]->qry(l,r);
if(t<pr.fi||pr.se<t){
ans+=(1<<k);
tie(l,r)=pr;
}
}
pf("%d\n",ans+1);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:52:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | sf("%d%d%d",&n,&k,&m);
| ^
Main.cpp:55:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | int a,b;sf("%d%d",&a,&b);
| ^
Main.cpp:83:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | sf("%d",&q);
| ^
Main.cpp:85:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | int s,t;sf("%d%d",&s,&t);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
3 ms |
852 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
3 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
3 ms |
852 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
3 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
18 ms |
4308 KB |
Output is correct |
14 |
Correct |
17 ms |
4248 KB |
Output is correct |
15 |
Correct |
11 ms |
4324 KB |
Output is correct |
16 |
Correct |
11 ms |
4308 KB |
Output is correct |
17 |
Correct |
15 ms |
4324 KB |
Output is correct |
18 |
Correct |
11 ms |
4208 KB |
Output is correct |
19 |
Correct |
14 ms |
4116 KB |
Output is correct |
20 |
Correct |
10 ms |
4280 KB |
Output is correct |
21 |
Correct |
9 ms |
4308 KB |
Output is correct |
22 |
Correct |
14 ms |
4320 KB |
Output is correct |
23 |
Correct |
14 ms |
4248 KB |
Output is correct |
24 |
Correct |
14 ms |
4308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
811 ms |
200484 KB |
Output is correct |
2 |
Correct |
782 ms |
200428 KB |
Output is correct |
3 |
Correct |
866 ms |
200504 KB |
Output is correct |
4 |
Correct |
769 ms |
200396 KB |
Output is correct |
5 |
Correct |
517 ms |
200596 KB |
Output is correct |
6 |
Correct |
737 ms |
200444 KB |
Output is correct |
7 |
Correct |
501 ms |
200400 KB |
Output is correct |
8 |
Correct |
485 ms |
198536 KB |
Output is correct |
9 |
Correct |
516 ms |
200500 KB |
Output is correct |
10 |
Correct |
736 ms |
200464 KB |
Output is correct |
11 |
Correct |
673 ms |
200488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1088 ms |
200852 KB |
Output is correct |
2 |
Correct |
776 ms |
203528 KB |
Output is correct |
3 |
Correct |
1306 ms |
202464 KB |
Output is correct |
4 |
Correct |
663 ms |
203108 KB |
Output is correct |
5 |
Correct |
617 ms |
201336 KB |
Output is correct |
6 |
Correct |
606 ms |
203304 KB |
Output is correct |
7 |
Correct |
1060 ms |
203468 KB |
Output is correct |
8 |
Correct |
1068 ms |
203508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
701 ms |
200528 KB |
Output is correct |
2 |
Correct |
1648 ms |
201184 KB |
Output is correct |
3 |
Correct |
1563 ms |
201968 KB |
Output is correct |
4 |
Correct |
1443 ms |
201552 KB |
Output is correct |
5 |
Correct |
1128 ms |
201280 KB |
Output is correct |
6 |
Correct |
1135 ms |
201180 KB |
Output is correct |
7 |
Correct |
816 ms |
202392 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
12 ms |
4308 KB |
Output is correct |
10 |
Correct |
685 ms |
202680 KB |
Output is correct |
11 |
Correct |
751 ms |
203324 KB |
Output is correct |
12 |
Correct |
794 ms |
201508 KB |
Output is correct |
13 |
Correct |
789 ms |
203372 KB |
Output is correct |
14 |
Correct |
2 ms |
980 KB |
Output is correct |
15 |
Correct |
17 ms |
4292 KB |
Output is correct |
16 |
Correct |
782 ms |
202792 KB |
Output is correct |
17 |
Correct |
1414 ms |
203600 KB |
Output is correct |
18 |
Correct |
1353 ms |
203628 KB |
Output is correct |
19 |
Correct |
1164 ms |
203560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
3 ms |
852 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
3 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
18 ms |
4308 KB |
Output is correct |
14 |
Correct |
17 ms |
4248 KB |
Output is correct |
15 |
Correct |
11 ms |
4324 KB |
Output is correct |
16 |
Correct |
11 ms |
4308 KB |
Output is correct |
17 |
Correct |
15 ms |
4324 KB |
Output is correct |
18 |
Correct |
11 ms |
4208 KB |
Output is correct |
19 |
Correct |
14 ms |
4116 KB |
Output is correct |
20 |
Correct |
10 ms |
4280 KB |
Output is correct |
21 |
Correct |
9 ms |
4308 KB |
Output is correct |
22 |
Correct |
14 ms |
4320 KB |
Output is correct |
23 |
Correct |
14 ms |
4248 KB |
Output is correct |
24 |
Correct |
14 ms |
4308 KB |
Output is correct |
25 |
Correct |
811 ms |
200484 KB |
Output is correct |
26 |
Correct |
782 ms |
200428 KB |
Output is correct |
27 |
Correct |
866 ms |
200504 KB |
Output is correct |
28 |
Correct |
769 ms |
200396 KB |
Output is correct |
29 |
Correct |
517 ms |
200596 KB |
Output is correct |
30 |
Correct |
737 ms |
200444 KB |
Output is correct |
31 |
Correct |
501 ms |
200400 KB |
Output is correct |
32 |
Correct |
485 ms |
198536 KB |
Output is correct |
33 |
Correct |
516 ms |
200500 KB |
Output is correct |
34 |
Correct |
736 ms |
200464 KB |
Output is correct |
35 |
Correct |
673 ms |
200488 KB |
Output is correct |
36 |
Correct |
1088 ms |
200852 KB |
Output is correct |
37 |
Correct |
776 ms |
203528 KB |
Output is correct |
38 |
Correct |
1306 ms |
202464 KB |
Output is correct |
39 |
Correct |
663 ms |
203108 KB |
Output is correct |
40 |
Correct |
617 ms |
201336 KB |
Output is correct |
41 |
Correct |
606 ms |
203304 KB |
Output is correct |
42 |
Correct |
1060 ms |
203468 KB |
Output is correct |
43 |
Correct |
1068 ms |
203508 KB |
Output is correct |
44 |
Correct |
701 ms |
200528 KB |
Output is correct |
45 |
Correct |
1648 ms |
201184 KB |
Output is correct |
46 |
Correct |
1563 ms |
201968 KB |
Output is correct |
47 |
Correct |
1443 ms |
201552 KB |
Output is correct |
48 |
Correct |
1128 ms |
201280 KB |
Output is correct |
49 |
Correct |
1135 ms |
201180 KB |
Output is correct |
50 |
Correct |
816 ms |
202392 KB |
Output is correct |
51 |
Correct |
2 ms |
852 KB |
Output is correct |
52 |
Correct |
12 ms |
4308 KB |
Output is correct |
53 |
Correct |
685 ms |
202680 KB |
Output is correct |
54 |
Correct |
751 ms |
203324 KB |
Output is correct |
55 |
Correct |
794 ms |
201508 KB |
Output is correct |
56 |
Correct |
789 ms |
203372 KB |
Output is correct |
57 |
Correct |
2 ms |
980 KB |
Output is correct |
58 |
Correct |
17 ms |
4292 KB |
Output is correct |
59 |
Correct |
782 ms |
202792 KB |
Output is correct |
60 |
Correct |
1414 ms |
203600 KB |
Output is correct |
61 |
Correct |
1353 ms |
203628 KB |
Output is correct |
62 |
Correct |
1164 ms |
203560 KB |
Output is correct |
63 |
Correct |
1378 ms |
202164 KB |
Output is correct |
64 |
Correct |
1632 ms |
202504 KB |
Output is correct |
65 |
Correct |
1457 ms |
202424 KB |
Output is correct |
66 |
Correct |
535 ms |
203596 KB |
Output is correct |
67 |
Correct |
1244 ms |
203544 KB |
Output is correct |
68 |
Correct |
907 ms |
201516 KB |
Output is correct |
69 |
Correct |
616 ms |
203340 KB |
Output is correct |
70 |
Correct |
930 ms |
203608 KB |
Output is correct |
71 |
Correct |
1399 ms |
203524 KB |
Output is correct |