#include <bits/stdc++.h>
using namespace std;
int N;
int M,Q;
int A,B;
int K;
int lt[100100];
int rt[100100];
int l[100100][30];
int r[100100][30];
struct node{
int s,e,m;
node *l,*r;
int le,ri;
int d;
node(int S, int E, int D){
s = S;
e = E;
m = (s + e)/2;
d = D;
if(s == e){
le = ::l[s][d];
ri = ::r[s][d];
}
else{
l = new node(s,m,d);
r = new node(m + 1,e,d);
le = min(l -> le, r -> le);
ri = max(l -> ri, r -> ri);
}
}
pair<int,int> query(int S, int E){
if(S <= s && e <= E){
return make_pair(le,ri);
}
pair<int,int> ii = make_pair(S,E);
pair<int,int> ii1;
if(S <= m){
ii1 = l -> query(S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second,ii1.second);
}
if(m < E){
ii1 = r -> query(S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second, ii1.second);
}
return ii;
}
} *root[30];
int main(){
scanf(" %d",&N);
scanf(" %d",&K);
scanf(" %d",&M);
for(int i = 1; i <= N; i++){
rt[i] = i;
lt[i] = i;
}
for(int i = 1; i <= M; i++){
scanf(" %d",&A);
scanf(" %d",&B);
if(B > A){
rt[A] = max(rt[A],B);
}
else if(B < A){
lt[A] = min(lt[A],B);
}
}
deque<pair<int,int>> dq;
for(int i = 1; i <= N; i++){
while(!dq.empty() && dq.front().first == i){
dq.pop_front();
}
while(!dq.empty() && dq.back().second <= rt[i]){
dq.pop_back();
}
dq.push_back(make_pair(i + K,rt[i]) );
r[i][0] = dq.front().second;
}
dq.clear();
for(int i = N; i >= 1; i--){
while(!dq.empty() && dq.front().first == i){
dq.pop_front();
}
while(!dq.empty() && dq.back() .second >= lt[i]){
dq.pop_back();
}
dq.push_back(make_pair(i - K,lt[i]));
l[i][0] = dq.front().second;
}
root[0] = new node(1,N,0);
for(int j = 1; j <= 25; j++){
for(int i = 1; i <= N; i++){
pair<int,int> ii = root[j - 1] -> query(i,i);
ii = root[j - 1] -> query(ii.first,ii.second);
l[i][j] = ii.first;
r[i][j] = ii.second;
}
root[j] = new node(1,N,j);
}
scanf(" %d",&Q);
for(int i = 0; i < Q; i++){
scanf(" %d",&A);
scanf(" %d",&B);
int sum = 0;
pair<int,int> ii = root[25] -> query(A,A);
pair<int,int> temp;
if(ii.first > B || B > ii.second){
printf("-1\n");
}
else{
ii = make_pair(A,A);
temp = make_pair(A,A);
for(int i = 25; i >= 0; i--){
temp = root[i] -> query(ii.first, ii.second);
if(temp.first > B || B > temp.second){
ii = temp;
sum += (1<<i);
}
}
printf("%d\n",sum + 1);
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf(" %d",&K);
| ~~~~~^~~~~~~~~~
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf(" %d",&M);
| ~~~~~^~~~~~~~~~
Main.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf(" %d",&A);
| ~~~~~^~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf(" %d",&B);
| ~~~~~^~~~~~~~~~
Main.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf(" %d",&Q);
| ~~~~~^~~~~~~~~~
Main.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf(" %d",&A);
| ~~~~~^~~~~~~~~~
Main.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | scanf(" %d",&B);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3516 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
2 ms |
3420 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3516 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
2 ms |
3420 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
13 |
Correct |
18 ms |
11096 KB |
Output is correct |
14 |
Correct |
17 ms |
11100 KB |
Output is correct |
15 |
Correct |
12 ms |
11100 KB |
Output is correct |
16 |
Correct |
9 ms |
11100 KB |
Output is correct |
17 |
Correct |
16 ms |
11252 KB |
Output is correct |
18 |
Correct |
11 ms |
11280 KB |
Output is correct |
19 |
Correct |
14 ms |
10844 KB |
Output is correct |
20 |
Correct |
11 ms |
11100 KB |
Output is correct |
21 |
Correct |
8 ms |
11096 KB |
Output is correct |
22 |
Correct |
16 ms |
11096 KB |
Output is correct |
23 |
Correct |
15 ms |
11100 KB |
Output is correct |
24 |
Correct |
14 ms |
11340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
814 ms |
351276 KB |
Output is correct |
2 |
Correct |
717 ms |
351344 KB |
Output is correct |
3 |
Correct |
755 ms |
351236 KB |
Output is correct |
4 |
Correct |
704 ms |
351056 KB |
Output is correct |
5 |
Correct |
470 ms |
352596 KB |
Output is correct |
6 |
Correct |
690 ms |
352420 KB |
Output is correct |
7 |
Correct |
476 ms |
352304 KB |
Output is correct |
8 |
Correct |
467 ms |
348028 KB |
Output is correct |
9 |
Correct |
458 ms |
351752 KB |
Output is correct |
10 |
Correct |
684 ms |
352460 KB |
Output is correct |
11 |
Correct |
612 ms |
352592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1367 ms |
352212 KB |
Output is correct |
2 |
Correct |
669 ms |
353360 KB |
Output is correct |
3 |
Correct |
1288 ms |
352168 KB |
Output is correct |
4 |
Correct |
827 ms |
352856 KB |
Output is correct |
5 |
Correct |
723 ms |
349912 KB |
Output is correct |
6 |
Correct |
657 ms |
353184 KB |
Output is correct |
7 |
Correct |
1242 ms |
353460 KB |
Output is correct |
8 |
Correct |
1195 ms |
353360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
694 ms |
353148 KB |
Output is correct |
2 |
Correct |
1877 ms |
352528 KB |
Output is correct |
3 |
Correct |
1791 ms |
351952 KB |
Output is correct |
4 |
Correct |
1612 ms |
351328 KB |
Output is correct |
5 |
Correct |
1189 ms |
351080 KB |
Output is correct |
6 |
Correct |
1218 ms |
350828 KB |
Output is correct |
7 |
Correct |
1002 ms |
352236 KB |
Output is correct |
8 |
Correct |
3 ms |
3416 KB |
Output is correct |
9 |
Correct |
14 ms |
11100 KB |
Output is correct |
10 |
Correct |
675 ms |
352560 KB |
Output is correct |
11 |
Correct |
837 ms |
353364 KB |
Output is correct |
12 |
Correct |
890 ms |
349788 KB |
Output is correct |
13 |
Correct |
939 ms |
352996 KB |
Output is correct |
14 |
Correct |
2 ms |
3420 KB |
Output is correct |
15 |
Correct |
18 ms |
11092 KB |
Output is correct |
16 |
Correct |
798 ms |
352976 KB |
Output is correct |
17 |
Correct |
1661 ms |
353592 KB |
Output is correct |
18 |
Correct |
1429 ms |
353620 KB |
Output is correct |
19 |
Correct |
1168 ms |
353360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3516 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
2 ms |
3420 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
13 |
Correct |
18 ms |
11096 KB |
Output is correct |
14 |
Correct |
17 ms |
11100 KB |
Output is correct |
15 |
Correct |
12 ms |
11100 KB |
Output is correct |
16 |
Correct |
9 ms |
11100 KB |
Output is correct |
17 |
Correct |
16 ms |
11252 KB |
Output is correct |
18 |
Correct |
11 ms |
11280 KB |
Output is correct |
19 |
Correct |
14 ms |
10844 KB |
Output is correct |
20 |
Correct |
11 ms |
11100 KB |
Output is correct |
21 |
Correct |
8 ms |
11096 KB |
Output is correct |
22 |
Correct |
16 ms |
11096 KB |
Output is correct |
23 |
Correct |
15 ms |
11100 KB |
Output is correct |
24 |
Correct |
14 ms |
11340 KB |
Output is correct |
25 |
Correct |
814 ms |
351276 KB |
Output is correct |
26 |
Correct |
717 ms |
351344 KB |
Output is correct |
27 |
Correct |
755 ms |
351236 KB |
Output is correct |
28 |
Correct |
704 ms |
351056 KB |
Output is correct |
29 |
Correct |
470 ms |
352596 KB |
Output is correct |
30 |
Correct |
690 ms |
352420 KB |
Output is correct |
31 |
Correct |
476 ms |
352304 KB |
Output is correct |
32 |
Correct |
467 ms |
348028 KB |
Output is correct |
33 |
Correct |
458 ms |
351752 KB |
Output is correct |
34 |
Correct |
684 ms |
352460 KB |
Output is correct |
35 |
Correct |
612 ms |
352592 KB |
Output is correct |
36 |
Correct |
1367 ms |
352212 KB |
Output is correct |
37 |
Correct |
669 ms |
353360 KB |
Output is correct |
38 |
Correct |
1288 ms |
352168 KB |
Output is correct |
39 |
Correct |
827 ms |
352856 KB |
Output is correct |
40 |
Correct |
723 ms |
349912 KB |
Output is correct |
41 |
Correct |
657 ms |
353184 KB |
Output is correct |
42 |
Correct |
1242 ms |
353460 KB |
Output is correct |
43 |
Correct |
1195 ms |
353360 KB |
Output is correct |
44 |
Correct |
694 ms |
353148 KB |
Output is correct |
45 |
Correct |
1877 ms |
352528 KB |
Output is correct |
46 |
Correct |
1791 ms |
351952 KB |
Output is correct |
47 |
Correct |
1612 ms |
351328 KB |
Output is correct |
48 |
Correct |
1189 ms |
351080 KB |
Output is correct |
49 |
Correct |
1218 ms |
350828 KB |
Output is correct |
50 |
Correct |
1002 ms |
352236 KB |
Output is correct |
51 |
Correct |
3 ms |
3416 KB |
Output is correct |
52 |
Correct |
14 ms |
11100 KB |
Output is correct |
53 |
Correct |
675 ms |
352560 KB |
Output is correct |
54 |
Correct |
837 ms |
353364 KB |
Output is correct |
55 |
Correct |
890 ms |
349788 KB |
Output is correct |
56 |
Correct |
939 ms |
352996 KB |
Output is correct |
57 |
Correct |
2 ms |
3420 KB |
Output is correct |
58 |
Correct |
18 ms |
11092 KB |
Output is correct |
59 |
Correct |
798 ms |
352976 KB |
Output is correct |
60 |
Correct |
1661 ms |
353592 KB |
Output is correct |
61 |
Correct |
1429 ms |
353620 KB |
Output is correct |
62 |
Correct |
1168 ms |
353360 KB |
Output is correct |
63 |
Correct |
1587 ms |
352024 KB |
Output is correct |
64 |
Correct |
1893 ms |
352008 KB |
Output is correct |
65 |
Correct |
1649 ms |
352204 KB |
Output is correct |
66 |
Correct |
501 ms |
353360 KB |
Output is correct |
67 |
Correct |
1273 ms |
353444 KB |
Output is correct |
68 |
Correct |
1018 ms |
349912 KB |
Output is correct |
69 |
Correct |
699 ms |
353360 KB |
Output is correct |
70 |
Correct |
1008 ms |
353104 KB |
Output is correct |
71 |
Correct |
1759 ms |
353368 KB |
Output is correct |