#include<bits/stdc++.h>
using namespace std;
int n, k, m, q;
int a, b;
vector<int> l[100005], r[100005];
priority_queue< pair<int,int> > pq;
int L[100005][20][20], R[100005][20][20];
int LOG2[100005];
pair<int,int> findRange(int l, int r, int j) {
pair<int,int> rv;
int LOG = LOG2[r-l+1];
rv.first = min(L[l][j][LOG], L[r-(1<<LOG)+1][j][LOG]);
rv.second = max(R[l][j][LOG], R[r-(1<<LOG)+1][j][LOG]);
return rv;
}
int main() {
ios::sync_with_stdio(false);
for(int i=2; i<=1e5; i++) LOG2[i] = LOG2[i/2] + 1;
cin >> n >> k >> m;
for(int i=0; i<m; i++) {
cin >> a >> b;
if(a < b) {
l[a].push_back(b);
} else {
r[a].push_back(b);
}
}
for(int i=1; i<=n; i++) {
for(int j:l[i]) pq.push({j, i});
while(!pq.empty() && pq.top().second<i-k+1) pq.pop();
R[i][0][0] = i;
if(!pq.empty()) {
R[i][0][0] = max(R[i][0][0], pq.top().first);
}
}
while(!pq.empty()) pq.pop();
for(int i=n; i>=1; i--) {
for(int j:r[i]) pq.push({-j, i});
while(!pq.empty() && pq.top().second>i+k-1) pq.pop();
L[i][0][0] = i;
if(!pq.empty()) {
L[i][0][0] = min(L[i][0][0], -pq.top().first);
}
}
for(int j=0; j<=19; j++) {
if(j>0)
for(int i=1; i<=n; i++) {
int LL = L[i][j-1][0];
int RR = R[i][j-1][0];
int LOG = LOG2[RR-LL+1];
L[i][j][0] = min(L[LL][j-1][LOG], L[RR-(1<<LOG)+1][j-1][LOG]);
R[i][j][0] = max(R[LL][j-1][LOG], R[RR-(1<<LOG)+1][j-1][LOG]);
}
for(int k=1; k<=19; k++) {
for(int i=1; i<=n; i++) {
if(i+(1<<k)-1 > n) break;
L[i][j][k] = min(L[i][j][k-1], L[i+(1<<(k-1))][j][k-1]);
R[i][j][k] = max(R[i][j][k-1], R[i+(1<<(k-1))][j][k-1]);
}
}
}
cin >> q;
while(q--) {
cin >> a >> b;
int ans = 0;
if(L[a][19][0] > b || R[a][19][0] < b) {
cout << "-1\n";
} else {
int ans = 0, lo = a, hi = a;
for(int j=19; j>=0; j--) {
pair<int,int> range = findRange(lo, hi, j);
if(range.first > b || range.second < b) {
ans += (1<<j);
lo = range.first;
hi = range.second;
}
}
cout << ans+1 << "\n";
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:68:7: warning: unused variable 'ans' [-Wunused-variable]
68 | int ans = 0;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6356 KB |
Output is correct |
2 |
Correct |
3 ms |
6356 KB |
Output is correct |
3 |
Correct |
4 ms |
6320 KB |
Output is correct |
4 |
Correct |
4 ms |
6356 KB |
Output is correct |
5 |
Correct |
4 ms |
6324 KB |
Output is correct |
6 |
Correct |
4 ms |
6320 KB |
Output is correct |
7 |
Correct |
4 ms |
6324 KB |
Output is correct |
8 |
Correct |
4 ms |
6356 KB |
Output is correct |
9 |
Correct |
4 ms |
6324 KB |
Output is correct |
10 |
Correct |
3 ms |
5332 KB |
Output is correct |
11 |
Correct |
4 ms |
6356 KB |
Output is correct |
12 |
Correct |
5 ms |
6324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6356 KB |
Output is correct |
2 |
Correct |
3 ms |
6356 KB |
Output is correct |
3 |
Correct |
4 ms |
6320 KB |
Output is correct |
4 |
Correct |
4 ms |
6356 KB |
Output is correct |
5 |
Correct |
4 ms |
6324 KB |
Output is correct |
6 |
Correct |
4 ms |
6320 KB |
Output is correct |
7 |
Correct |
4 ms |
6324 KB |
Output is correct |
8 |
Correct |
4 ms |
6356 KB |
Output is correct |
9 |
Correct |
4 ms |
6324 KB |
Output is correct |
10 |
Correct |
3 ms |
5332 KB |
Output is correct |
11 |
Correct |
4 ms |
6356 KB |
Output is correct |
12 |
Correct |
5 ms |
6324 KB |
Output is correct |
13 |
Correct |
10 ms |
11732 KB |
Output is correct |
14 |
Correct |
11 ms |
11768 KB |
Output is correct |
15 |
Correct |
7 ms |
11712 KB |
Output is correct |
16 |
Correct |
11 ms |
11712 KB |
Output is correct |
17 |
Correct |
11 ms |
11760 KB |
Output is correct |
18 |
Correct |
15 ms |
11752 KB |
Output is correct |
19 |
Correct |
12 ms |
11476 KB |
Output is correct |
20 |
Correct |
14 ms |
11708 KB |
Output is correct |
21 |
Correct |
9 ms |
11752 KB |
Output is correct |
22 |
Correct |
12 ms |
11712 KB |
Output is correct |
23 |
Correct |
11 ms |
11756 KB |
Output is correct |
24 |
Correct |
11 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1016 ms |
322088 KB |
Output is correct |
2 |
Correct |
1002 ms |
322040 KB |
Output is correct |
3 |
Correct |
1012 ms |
322648 KB |
Output is correct |
4 |
Correct |
1047 ms |
321692 KB |
Output is correct |
5 |
Correct |
1034 ms |
325276 KB |
Output is correct |
6 |
Correct |
1036 ms |
327976 KB |
Output is correct |
7 |
Correct |
1016 ms |
327708 KB |
Output is correct |
8 |
Correct |
1055 ms |
319480 KB |
Output is correct |
9 |
Correct |
986 ms |
322484 KB |
Output is correct |
10 |
Correct |
1037 ms |
325748 KB |
Output is correct |
11 |
Correct |
1042 ms |
325696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1059 ms |
323288 KB |
Output is correct |
2 |
Correct |
1083 ms |
325984 KB |
Output is correct |
3 |
Correct |
1118 ms |
324088 KB |
Output is correct |
4 |
Correct |
1110 ms |
328248 KB |
Output is correct |
5 |
Correct |
1077 ms |
322824 KB |
Output is correct |
6 |
Correct |
1167 ms |
325848 KB |
Output is correct |
7 |
Correct |
1119 ms |
326456 KB |
Output is correct |
8 |
Correct |
1148 ms |
326464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1093 ms |
325708 KB |
Output is correct |
2 |
Correct |
1145 ms |
324668 KB |
Output is correct |
3 |
Correct |
1143 ms |
322140 KB |
Output is correct |
4 |
Correct |
1103 ms |
320440 KB |
Output is correct |
5 |
Correct |
1114 ms |
319452 KB |
Output is correct |
6 |
Correct |
1064 ms |
319180 KB |
Output is correct |
7 |
Correct |
1067 ms |
324484 KB |
Output is correct |
8 |
Correct |
4 ms |
6356 KB |
Output is correct |
9 |
Correct |
11 ms |
11860 KB |
Output is correct |
10 |
Correct |
1028 ms |
325012 KB |
Output is correct |
11 |
Correct |
1118 ms |
325672 KB |
Output is correct |
12 |
Correct |
1098 ms |
322436 KB |
Output is correct |
13 |
Correct |
1127 ms |
325824 KB |
Output is correct |
14 |
Correct |
4 ms |
6356 KB |
Output is correct |
15 |
Correct |
11 ms |
11732 KB |
Output is correct |
16 |
Correct |
1018 ms |
323700 KB |
Output is correct |
17 |
Correct |
1170 ms |
326120 KB |
Output is correct |
18 |
Correct |
1163 ms |
325976 KB |
Output is correct |
19 |
Correct |
1151 ms |
326036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6356 KB |
Output is correct |
2 |
Correct |
3 ms |
6356 KB |
Output is correct |
3 |
Correct |
4 ms |
6320 KB |
Output is correct |
4 |
Correct |
4 ms |
6356 KB |
Output is correct |
5 |
Correct |
4 ms |
6324 KB |
Output is correct |
6 |
Correct |
4 ms |
6320 KB |
Output is correct |
7 |
Correct |
4 ms |
6324 KB |
Output is correct |
8 |
Correct |
4 ms |
6356 KB |
Output is correct |
9 |
Correct |
4 ms |
6324 KB |
Output is correct |
10 |
Correct |
3 ms |
5332 KB |
Output is correct |
11 |
Correct |
4 ms |
6356 KB |
Output is correct |
12 |
Correct |
5 ms |
6324 KB |
Output is correct |
13 |
Correct |
10 ms |
11732 KB |
Output is correct |
14 |
Correct |
11 ms |
11768 KB |
Output is correct |
15 |
Correct |
7 ms |
11712 KB |
Output is correct |
16 |
Correct |
11 ms |
11712 KB |
Output is correct |
17 |
Correct |
11 ms |
11760 KB |
Output is correct |
18 |
Correct |
15 ms |
11752 KB |
Output is correct |
19 |
Correct |
12 ms |
11476 KB |
Output is correct |
20 |
Correct |
14 ms |
11708 KB |
Output is correct |
21 |
Correct |
9 ms |
11752 KB |
Output is correct |
22 |
Correct |
12 ms |
11712 KB |
Output is correct |
23 |
Correct |
11 ms |
11756 KB |
Output is correct |
24 |
Correct |
11 ms |
11796 KB |
Output is correct |
25 |
Correct |
1016 ms |
322088 KB |
Output is correct |
26 |
Correct |
1002 ms |
322040 KB |
Output is correct |
27 |
Correct |
1012 ms |
322648 KB |
Output is correct |
28 |
Correct |
1047 ms |
321692 KB |
Output is correct |
29 |
Correct |
1034 ms |
325276 KB |
Output is correct |
30 |
Correct |
1036 ms |
327976 KB |
Output is correct |
31 |
Correct |
1016 ms |
327708 KB |
Output is correct |
32 |
Correct |
1055 ms |
319480 KB |
Output is correct |
33 |
Correct |
986 ms |
322484 KB |
Output is correct |
34 |
Correct |
1037 ms |
325748 KB |
Output is correct |
35 |
Correct |
1042 ms |
325696 KB |
Output is correct |
36 |
Correct |
1059 ms |
323288 KB |
Output is correct |
37 |
Correct |
1083 ms |
325984 KB |
Output is correct |
38 |
Correct |
1118 ms |
324088 KB |
Output is correct |
39 |
Correct |
1110 ms |
328248 KB |
Output is correct |
40 |
Correct |
1077 ms |
322824 KB |
Output is correct |
41 |
Correct |
1167 ms |
325848 KB |
Output is correct |
42 |
Correct |
1119 ms |
326456 KB |
Output is correct |
43 |
Correct |
1148 ms |
326464 KB |
Output is correct |
44 |
Correct |
1093 ms |
325708 KB |
Output is correct |
45 |
Correct |
1145 ms |
324668 KB |
Output is correct |
46 |
Correct |
1143 ms |
322140 KB |
Output is correct |
47 |
Correct |
1103 ms |
320440 KB |
Output is correct |
48 |
Correct |
1114 ms |
319452 KB |
Output is correct |
49 |
Correct |
1064 ms |
319180 KB |
Output is correct |
50 |
Correct |
1067 ms |
324484 KB |
Output is correct |
51 |
Correct |
4 ms |
6356 KB |
Output is correct |
52 |
Correct |
11 ms |
11860 KB |
Output is correct |
53 |
Correct |
1028 ms |
325012 KB |
Output is correct |
54 |
Correct |
1118 ms |
325672 KB |
Output is correct |
55 |
Correct |
1098 ms |
322436 KB |
Output is correct |
56 |
Correct |
1127 ms |
325824 KB |
Output is correct |
57 |
Correct |
4 ms |
6356 KB |
Output is correct |
58 |
Correct |
11 ms |
11732 KB |
Output is correct |
59 |
Correct |
1018 ms |
323700 KB |
Output is correct |
60 |
Correct |
1170 ms |
326120 KB |
Output is correct |
61 |
Correct |
1163 ms |
325976 KB |
Output is correct |
62 |
Correct |
1151 ms |
326036 KB |
Output is correct |
63 |
Correct |
1170 ms |
322276 KB |
Output is correct |
64 |
Correct |
1193 ms |
323080 KB |
Output is correct |
65 |
Correct |
1144 ms |
322512 KB |
Output is correct |
66 |
Correct |
1130 ms |
325956 KB |
Output is correct |
67 |
Correct |
1183 ms |
328784 KB |
Output is correct |
68 |
Correct |
1138 ms |
322696 KB |
Output is correct |
69 |
Correct |
1117 ms |
325940 KB |
Output is correct |
70 |
Correct |
1120 ms |
325604 KB |
Output is correct |
71 |
Correct |
1188 ms |
326596 KB |
Output is correct |