#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
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);
if(a<b)mx[0][a]=max(mx[0][a],b);
else 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))]);
}
}
sf("%d",&q);
for(int i=0;i<q;++i){
int s,t;sf("%d%d",&s,&t);
int l=s,r=s,ans=0;
while(t<l||r<t){
int nr=max(r,getmx(l-k+1,r)),nl=min(l,getmn(l,r+k-1));
if(nl==l&&nr==r){
ans=-1;break;
}
l=nl,r=nr;
++ans;
}
pf("%d\n",ans);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:30:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | sf("%d%d%d",&n,&k,&m);
| ^
Main.cpp:33:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | int a,b;sf("%d%d",&a,&b);
| ^
Main.cpp:43:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | sf("%d",&q);
| ^
Main.cpp:45:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | int s,t;sf("%d%d",&s,&t);
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
308 KB |
Output is correct |
13 |
Correct |
17 ms |
596 KB |
Output is correct |
14 |
Correct |
11 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
6 ms |
492 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
13484 KB |
Output is correct |
2 |
Correct |
21 ms |
13496 KB |
Output is correct |
3 |
Correct |
23 ms |
13652 KB |
Output is correct |
4 |
Correct |
22 ms |
13508 KB |
Output is correct |
5 |
Correct |
43 ms |
14888 KB |
Output is correct |
6 |
Correct |
41 ms |
14896 KB |
Output is correct |
7 |
Correct |
47 ms |
14648 KB |
Output is correct |
8 |
Correct |
31 ms |
13736 KB |
Output is correct |
9 |
Correct |
26 ms |
13752 KB |
Output is correct |
10 |
Correct |
47 ms |
14912 KB |
Output is correct |
11 |
Correct |
44 ms |
14896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2075 ms |
14224 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
15640 KB |
Output is correct |
2 |
Execution timed out |
2074 ms |
14176 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
308 KB |
Output is correct |
13 |
Correct |
17 ms |
596 KB |
Output is correct |
14 |
Correct |
11 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
6 ms |
492 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
23 ms |
13484 KB |
Output is correct |
26 |
Correct |
21 ms |
13496 KB |
Output is correct |
27 |
Correct |
23 ms |
13652 KB |
Output is correct |
28 |
Correct |
22 ms |
13508 KB |
Output is correct |
29 |
Correct |
43 ms |
14888 KB |
Output is correct |
30 |
Correct |
41 ms |
14896 KB |
Output is correct |
31 |
Correct |
47 ms |
14648 KB |
Output is correct |
32 |
Correct |
31 ms |
13736 KB |
Output is correct |
33 |
Correct |
26 ms |
13752 KB |
Output is correct |
34 |
Correct |
47 ms |
14912 KB |
Output is correct |
35 |
Correct |
44 ms |
14896 KB |
Output is correct |
36 |
Execution timed out |
2075 ms |
14224 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |