#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 200000;
const int LOG = 19;
int L[LOG+1][N+5], R[LOG+1][N+5];
struct Segment{
int lv[4*N+5], rv[4*N+5];
void init(int node, int l, int r, int t){
if(l == r){
lv[node] = L[t][l];
rv[node] = R[t][l];
return;
}
int mid = (l+r)/2;
init(node*2, l, mid, t);
init(node*2+1, mid+1, r, t);
lv[node] = min(lv[node*2], lv[node*2+1]);
rv[node] = max(rv[node*2], rv[node*2+1]);
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
if(tl > r || l > tr) return {N + 5, 0};
if(tl <= l && r <= tr) return {lv[node], rv[node]};
int mid = (l+r)/2;
pair <int, int> a = query(node*2, l, mid, tl, tr);
pair <int, int> b = query(node*2+1, mid+1, r, tl, tr);
return {min(a.first, b.first), max(a.second, b.second)};
}
} seg[LOG+1];
multiset <int> q;
vector <int> vec[N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, k, m;
cin >> n >> k >> m;
for(int i=1; i<=m; i++){
int l, r;
cin >> l >> r;
if(l <= r){
vec[l].push_back(r);
vec[min(l + k, r)].push_back(-r);
}
else{
swap(l, r);
vec[max(r - k + 1, l + 1)].push_back(l);
vec[r + 1].push_back(-l);
}
}
for(int i=1; i<=n; i++){
for(auto c : vec[i]){
if(c < 0){
q.erase(q.find(-c));
}
else{
q.insert(c);
}
}
if(q.empty()) L[0][i] = R[0][i] = i;
else{
L[0][i] = min(i, *q.begin());
R[0][i] = max(i, *q.rbegin());
}
}
seg[0].init(1, 1, n, 0);
for(int j=1; j<=LOG; j++){
for(int i=1; i<=n; i++){
pair <int, int> g = seg[j-1].query(1, 1, n, L[j-1][i], R[j-1][i]);
L[j][i] = g.first;
R[j][i] = g.second;
}
seg[j].init(1, 1, n, j);
}
int qrs;
cin >> qrs;
while(qrs--){
int s, t;
cin >> s >> t;
int x = 0;
int sl = s, sr = s;
for(int j=LOG; j>=0; j--){
pair <int, int> h = seg[j].query(1, 1, n, sl, sr);
if(h.first > t || h.second < t){
x += (1 << j);
sl = h.first;
sr = h.second;
}
}
pair <int, int> h = seg[0].query(1, 1, n, sl, sr);
if(h.first <= t && t <= h.second) cout << x + 1 << "\n";
else cout << "-1\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5716 KB |
Output is correct |
2 |
Correct |
4 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5716 KB |
Output is correct |
7 |
Correct |
4 ms |
5668 KB |
Output is correct |
8 |
Correct |
4 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5716 KB |
Output is correct |
2 |
Correct |
4 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5716 KB |
Output is correct |
7 |
Correct |
4 ms |
5668 KB |
Output is correct |
8 |
Correct |
4 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
13 |
Correct |
12 ms |
6612 KB |
Output is correct |
14 |
Correct |
11 ms |
6612 KB |
Output is correct |
15 |
Correct |
8 ms |
6484 KB |
Output is correct |
16 |
Correct |
7 ms |
6636 KB |
Output is correct |
17 |
Correct |
13 ms |
6572 KB |
Output is correct |
18 |
Correct |
7 ms |
6612 KB |
Output is correct |
19 |
Correct |
12 ms |
6868 KB |
Output is correct |
20 |
Correct |
9 ms |
6652 KB |
Output is correct |
21 |
Correct |
5 ms |
6600 KB |
Output is correct |
22 |
Correct |
9 ms |
6612 KB |
Output is correct |
23 |
Correct |
15 ms |
6604 KB |
Output is correct |
24 |
Correct |
11 ms |
6572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
366 ms |
65996 KB |
Output is correct |
2 |
Correct |
322 ms |
66008 KB |
Output is correct |
3 |
Correct |
375 ms |
66348 KB |
Output is correct |
4 |
Correct |
323 ms |
65928 KB |
Output is correct |
5 |
Correct |
180 ms |
71000 KB |
Output is correct |
6 |
Correct |
341 ms |
67580 KB |
Output is correct |
7 |
Correct |
160 ms |
72896 KB |
Output is correct |
8 |
Correct |
110 ms |
68012 KB |
Output is correct |
9 |
Correct |
107 ms |
68392 KB |
Output is correct |
10 |
Correct |
350 ms |
68684 KB |
Output is correct |
11 |
Correct |
312 ms |
68664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
561 ms |
68988 KB |
Output is correct |
2 |
Correct |
441 ms |
71692 KB |
Output is correct |
3 |
Correct |
641 ms |
65676 KB |
Output is correct |
4 |
Correct |
258 ms |
73332 KB |
Output is correct |
5 |
Correct |
346 ms |
73784 KB |
Output is correct |
6 |
Correct |
274 ms |
73900 KB |
Output is correct |
7 |
Correct |
619 ms |
69248 KB |
Output is correct |
8 |
Correct |
489 ms |
69544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
554 ms |
71932 KB |
Output is correct |
2 |
Correct |
694 ms |
67300 KB |
Output is correct |
3 |
Correct |
686 ms |
65148 KB |
Output is correct |
4 |
Correct |
697 ms |
63844 KB |
Output is correct |
5 |
Correct |
543 ms |
63280 KB |
Output is correct |
6 |
Correct |
509 ms |
62924 KB |
Output is correct |
7 |
Correct |
427 ms |
72184 KB |
Output is correct |
8 |
Correct |
4 ms |
5716 KB |
Output is correct |
9 |
Correct |
9 ms |
6612 KB |
Output is correct |
10 |
Correct |
358 ms |
71880 KB |
Output is correct |
11 |
Correct |
464 ms |
73904 KB |
Output is correct |
12 |
Correct |
532 ms |
71968 KB |
Output is correct |
13 |
Correct |
439 ms |
73844 KB |
Output is correct |
14 |
Correct |
4 ms |
5716 KB |
Output is correct |
15 |
Correct |
11 ms |
6512 KB |
Output is correct |
16 |
Correct |
411 ms |
68692 KB |
Output is correct |
17 |
Correct |
665 ms |
69372 KB |
Output is correct |
18 |
Correct |
657 ms |
69528 KB |
Output is correct |
19 |
Correct |
568 ms |
69412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5716 KB |
Output is correct |
2 |
Correct |
4 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
4 ms |
5716 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5716 KB |
Output is correct |
7 |
Correct |
4 ms |
5668 KB |
Output is correct |
8 |
Correct |
4 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
13 |
Correct |
12 ms |
6612 KB |
Output is correct |
14 |
Correct |
11 ms |
6612 KB |
Output is correct |
15 |
Correct |
8 ms |
6484 KB |
Output is correct |
16 |
Correct |
7 ms |
6636 KB |
Output is correct |
17 |
Correct |
13 ms |
6572 KB |
Output is correct |
18 |
Correct |
7 ms |
6612 KB |
Output is correct |
19 |
Correct |
12 ms |
6868 KB |
Output is correct |
20 |
Correct |
9 ms |
6652 KB |
Output is correct |
21 |
Correct |
5 ms |
6600 KB |
Output is correct |
22 |
Correct |
9 ms |
6612 KB |
Output is correct |
23 |
Correct |
15 ms |
6604 KB |
Output is correct |
24 |
Correct |
11 ms |
6572 KB |
Output is correct |
25 |
Correct |
366 ms |
65996 KB |
Output is correct |
26 |
Correct |
322 ms |
66008 KB |
Output is correct |
27 |
Correct |
375 ms |
66348 KB |
Output is correct |
28 |
Correct |
323 ms |
65928 KB |
Output is correct |
29 |
Correct |
180 ms |
71000 KB |
Output is correct |
30 |
Correct |
341 ms |
67580 KB |
Output is correct |
31 |
Correct |
160 ms |
72896 KB |
Output is correct |
32 |
Correct |
110 ms |
68012 KB |
Output is correct |
33 |
Correct |
107 ms |
68392 KB |
Output is correct |
34 |
Correct |
350 ms |
68684 KB |
Output is correct |
35 |
Correct |
312 ms |
68664 KB |
Output is correct |
36 |
Correct |
561 ms |
68988 KB |
Output is correct |
37 |
Correct |
441 ms |
71692 KB |
Output is correct |
38 |
Correct |
641 ms |
65676 KB |
Output is correct |
39 |
Correct |
258 ms |
73332 KB |
Output is correct |
40 |
Correct |
346 ms |
73784 KB |
Output is correct |
41 |
Correct |
274 ms |
73900 KB |
Output is correct |
42 |
Correct |
619 ms |
69248 KB |
Output is correct |
43 |
Correct |
489 ms |
69544 KB |
Output is correct |
44 |
Correct |
554 ms |
71932 KB |
Output is correct |
45 |
Correct |
694 ms |
67300 KB |
Output is correct |
46 |
Correct |
686 ms |
65148 KB |
Output is correct |
47 |
Correct |
697 ms |
63844 KB |
Output is correct |
48 |
Correct |
543 ms |
63280 KB |
Output is correct |
49 |
Correct |
509 ms |
62924 KB |
Output is correct |
50 |
Correct |
427 ms |
72184 KB |
Output is correct |
51 |
Correct |
4 ms |
5716 KB |
Output is correct |
52 |
Correct |
9 ms |
6612 KB |
Output is correct |
53 |
Correct |
358 ms |
71880 KB |
Output is correct |
54 |
Correct |
464 ms |
73904 KB |
Output is correct |
55 |
Correct |
532 ms |
71968 KB |
Output is correct |
56 |
Correct |
439 ms |
73844 KB |
Output is correct |
57 |
Correct |
4 ms |
5716 KB |
Output is correct |
58 |
Correct |
11 ms |
6512 KB |
Output is correct |
59 |
Correct |
411 ms |
68692 KB |
Output is correct |
60 |
Correct |
665 ms |
69372 KB |
Output is correct |
61 |
Correct |
657 ms |
69528 KB |
Output is correct |
62 |
Correct |
568 ms |
69412 KB |
Output is correct |
63 |
Correct |
609 ms |
66788 KB |
Output is correct |
64 |
Correct |
724 ms |
67016 KB |
Output is correct |
65 |
Correct |
624 ms |
66800 KB |
Output is correct |
66 |
Correct |
236 ms |
71740 KB |
Output is correct |
67 |
Correct |
563 ms |
68432 KB |
Output is correct |
68 |
Correct |
496 ms |
69716 KB |
Output is correct |
69 |
Correct |
310 ms |
73876 KB |
Output is correct |
70 |
Correct |
561 ms |
69500 KB |
Output is correct |
71 |
Correct |
652 ms |
69616 KB |
Output is correct |