#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static int LamyIsCute = []() {
EmiliaMyWife
return 48763;
}();
const int LGN = 19, M = 2e5 + 25, N = 1e5 + 25;
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
struct segtree {
pair<int, int> arr[N << 1], tag[N];
int n;
void init(int _n) {
n = _n;
for(int i = 0; i < n * 2; i++)
arr[i] = {INF, -INF};
for(int i = 0; i < n; i++)
tag[i] = {INF, -INF};
}
void upd(int p, pair<int, int> v) {
arr[p] = arr[p] + v;
if(p < n)
tag[p] = tag[p] + v;
}
void push(int p) {
for(int h = __lg(p); ~h; h--) {
int i = p >> h;
upd(i, tag[i >> 1]);
upd(i ^ 1, tag[i >> 1]);
}
}
void pull(int p) {
for(; p > 1; p >>= 1)
arr[p >> 1] = arr[p] + arr[p ^ 1] + tag[p >> 1];
}
void edt(int l, int r, pair<int, int> v) {
int tl = l + n, tr = r + n - 1;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1)
upd(l++, v);
if(r & 1)
upd(--r, v);
}
pull(tl); pull(tr);
}
pair<int, int> que(int l, int r) {
pair<int, int> res = {INF, -INF};
push(l + n); push(r + n - 1);
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1)
res = res + arr[l++];
if(r & 1)
res = res + arr[--r];
}
return res;
}
} tree[LGN];
signed main() {
int n, k, m;
cin >> n >> k >> m;
vector<pair<int, int>> arr(m);
for(auto &[a, b] : arr)
cin >> a >> b;
for(int i = 0; i < LGN; i++)
tree[i].init(n + 1);
for(int i = 1; i <= n; i++)
tree[0].edt(i, i + 1, {i, i});
for(const auto &[a, b] : arr) {
if(a < b)
tree[0].edt(a, min(b + 1, a + k), {INF, b});
else
tree[0].edt(max(b, a - k + 1), a + 1, {b, -INF});
}
for(int i = 1; i < LGN; i++) {
for(int j = 1; j <= n; j++) {
auto [l, r] = tree[i - 1].que(j, j + 1);
auto [a, b] = tree[i - 1].que(l, r + 1);
tree[i].edt(j, j + 1, {a, b});
}
}
auto in = [&](int t, auto inter) {
return inter.first <= t && t <= inter.second;
};
int q;
cin >> q;
while(q--) {
int s, t;
cin >> s >> t;
if(!in(t, tree[LGN - 1].que(s, s + 1)))
cout << "-1\n";
else {
int res = 0;
pair<int, int> owo = {s, s};
for(int i = LGN - 1; ~i; i--) {
auto [l, r] = tree[i].que(owo.first, owo.second + 1);
if(!in(t, make_pair(l, r)))
owo = {l, r}, res |= 1 << i;
}
cout << res + 1 << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
44876 KB |
Output is correct |
2 |
Correct |
19 ms |
44876 KB |
Output is correct |
3 |
Correct |
19 ms |
44892 KB |
Output is correct |
4 |
Correct |
20 ms |
44884 KB |
Output is correct |
5 |
Correct |
20 ms |
44908 KB |
Output is correct |
6 |
Correct |
19 ms |
44832 KB |
Output is correct |
7 |
Correct |
20 ms |
44952 KB |
Output is correct |
8 |
Correct |
20 ms |
44876 KB |
Output is correct |
9 |
Correct |
21 ms |
44952 KB |
Output is correct |
10 |
Correct |
19 ms |
44932 KB |
Output is correct |
11 |
Correct |
20 ms |
44876 KB |
Output is correct |
12 |
Correct |
19 ms |
44892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
44876 KB |
Output is correct |
2 |
Correct |
19 ms |
44876 KB |
Output is correct |
3 |
Correct |
19 ms |
44892 KB |
Output is correct |
4 |
Correct |
20 ms |
44884 KB |
Output is correct |
5 |
Correct |
20 ms |
44908 KB |
Output is correct |
6 |
Correct |
19 ms |
44832 KB |
Output is correct |
7 |
Correct |
20 ms |
44952 KB |
Output is correct |
8 |
Correct |
20 ms |
44876 KB |
Output is correct |
9 |
Correct |
21 ms |
44952 KB |
Output is correct |
10 |
Correct |
19 ms |
44932 KB |
Output is correct |
11 |
Correct |
20 ms |
44876 KB |
Output is correct |
12 |
Correct |
19 ms |
44892 KB |
Output is correct |
13 |
Correct |
49 ms |
44876 KB |
Output is correct |
14 |
Correct |
42 ms |
44948 KB |
Output is correct |
15 |
Correct |
36 ms |
44952 KB |
Output is correct |
16 |
Correct |
33 ms |
44960 KB |
Output is correct |
17 |
Correct |
38 ms |
44952 KB |
Output is correct |
18 |
Correct |
39 ms |
44876 KB |
Output is correct |
19 |
Correct |
39 ms |
44836 KB |
Output is correct |
20 |
Correct |
41 ms |
44876 KB |
Output is correct |
21 |
Correct |
34 ms |
44876 KB |
Output is correct |
22 |
Correct |
42 ms |
44876 KB |
Output is correct |
23 |
Correct |
40 ms |
44952 KB |
Output is correct |
24 |
Correct |
39 ms |
45020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1226 ms |
45492 KB |
Output is correct |
2 |
Correct |
1223 ms |
45644 KB |
Output is correct |
3 |
Correct |
1260 ms |
45644 KB |
Output is correct |
4 |
Correct |
1239 ms |
45516 KB |
Output is correct |
5 |
Correct |
1223 ms |
46412 KB |
Output is correct |
6 |
Correct |
1333 ms |
46412 KB |
Output is correct |
7 |
Correct |
1207 ms |
46412 KB |
Output is correct |
8 |
Correct |
1161 ms |
45644 KB |
Output is correct |
9 |
Correct |
1170 ms |
45644 KB |
Output is correct |
10 |
Correct |
1209 ms |
46412 KB |
Output is correct |
11 |
Correct |
1257 ms |
46540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1635 ms |
45688 KB |
Output is correct |
2 |
Correct |
1249 ms |
46628 KB |
Output is correct |
3 |
Correct |
1625 ms |
45980 KB |
Output is correct |
4 |
Correct |
1518 ms |
46512 KB |
Output is correct |
5 |
Correct |
1527 ms |
46500 KB |
Output is correct |
6 |
Correct |
1500 ms |
46752 KB |
Output is correct |
7 |
Correct |
1524 ms |
46636 KB |
Output is correct |
8 |
Correct |
1695 ms |
46764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1296 ms |
46640 KB |
Output is correct |
2 |
Correct |
1960 ms |
45980 KB |
Output is correct |
3 |
Correct |
1816 ms |
45584 KB |
Output is correct |
4 |
Correct |
1827 ms |
45356 KB |
Output is correct |
5 |
Correct |
1587 ms |
45152 KB |
Output is correct |
6 |
Correct |
1585 ms |
45064 KB |
Output is correct |
7 |
Correct |
1583 ms |
45732 KB |
Output is correct |
8 |
Correct |
20 ms |
44888 KB |
Output is correct |
9 |
Correct |
41 ms |
44944 KB |
Output is correct |
10 |
Correct |
1262 ms |
46412 KB |
Output is correct |
11 |
Correct |
1557 ms |
46660 KB |
Output is correct |
12 |
Correct |
1527 ms |
46532 KB |
Output is correct |
13 |
Correct |
1548 ms |
46492 KB |
Output is correct |
14 |
Correct |
20 ms |
44876 KB |
Output is correct |
15 |
Correct |
42 ms |
44964 KB |
Output is correct |
16 |
Correct |
1248 ms |
46444 KB |
Output is correct |
17 |
Correct |
1822 ms |
46716 KB |
Output is correct |
18 |
Correct |
1726 ms |
46728 KB |
Output is correct |
19 |
Correct |
1645 ms |
46636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
44876 KB |
Output is correct |
2 |
Correct |
19 ms |
44876 KB |
Output is correct |
3 |
Correct |
19 ms |
44892 KB |
Output is correct |
4 |
Correct |
20 ms |
44884 KB |
Output is correct |
5 |
Correct |
20 ms |
44908 KB |
Output is correct |
6 |
Correct |
19 ms |
44832 KB |
Output is correct |
7 |
Correct |
20 ms |
44952 KB |
Output is correct |
8 |
Correct |
20 ms |
44876 KB |
Output is correct |
9 |
Correct |
21 ms |
44952 KB |
Output is correct |
10 |
Correct |
19 ms |
44932 KB |
Output is correct |
11 |
Correct |
20 ms |
44876 KB |
Output is correct |
12 |
Correct |
19 ms |
44892 KB |
Output is correct |
13 |
Correct |
49 ms |
44876 KB |
Output is correct |
14 |
Correct |
42 ms |
44948 KB |
Output is correct |
15 |
Correct |
36 ms |
44952 KB |
Output is correct |
16 |
Correct |
33 ms |
44960 KB |
Output is correct |
17 |
Correct |
38 ms |
44952 KB |
Output is correct |
18 |
Correct |
39 ms |
44876 KB |
Output is correct |
19 |
Correct |
39 ms |
44836 KB |
Output is correct |
20 |
Correct |
41 ms |
44876 KB |
Output is correct |
21 |
Correct |
34 ms |
44876 KB |
Output is correct |
22 |
Correct |
42 ms |
44876 KB |
Output is correct |
23 |
Correct |
40 ms |
44952 KB |
Output is correct |
24 |
Correct |
39 ms |
45020 KB |
Output is correct |
25 |
Correct |
1226 ms |
45492 KB |
Output is correct |
26 |
Correct |
1223 ms |
45644 KB |
Output is correct |
27 |
Correct |
1260 ms |
45644 KB |
Output is correct |
28 |
Correct |
1239 ms |
45516 KB |
Output is correct |
29 |
Correct |
1223 ms |
46412 KB |
Output is correct |
30 |
Correct |
1333 ms |
46412 KB |
Output is correct |
31 |
Correct |
1207 ms |
46412 KB |
Output is correct |
32 |
Correct |
1161 ms |
45644 KB |
Output is correct |
33 |
Correct |
1170 ms |
45644 KB |
Output is correct |
34 |
Correct |
1209 ms |
46412 KB |
Output is correct |
35 |
Correct |
1257 ms |
46540 KB |
Output is correct |
36 |
Correct |
1635 ms |
45688 KB |
Output is correct |
37 |
Correct |
1249 ms |
46628 KB |
Output is correct |
38 |
Correct |
1625 ms |
45980 KB |
Output is correct |
39 |
Correct |
1518 ms |
46512 KB |
Output is correct |
40 |
Correct |
1527 ms |
46500 KB |
Output is correct |
41 |
Correct |
1500 ms |
46752 KB |
Output is correct |
42 |
Correct |
1524 ms |
46636 KB |
Output is correct |
43 |
Correct |
1695 ms |
46764 KB |
Output is correct |
44 |
Correct |
1296 ms |
46640 KB |
Output is correct |
45 |
Correct |
1960 ms |
45980 KB |
Output is correct |
46 |
Correct |
1816 ms |
45584 KB |
Output is correct |
47 |
Correct |
1827 ms |
45356 KB |
Output is correct |
48 |
Correct |
1587 ms |
45152 KB |
Output is correct |
49 |
Correct |
1585 ms |
45064 KB |
Output is correct |
50 |
Correct |
1583 ms |
45732 KB |
Output is correct |
51 |
Correct |
20 ms |
44888 KB |
Output is correct |
52 |
Correct |
41 ms |
44944 KB |
Output is correct |
53 |
Correct |
1262 ms |
46412 KB |
Output is correct |
54 |
Correct |
1557 ms |
46660 KB |
Output is correct |
55 |
Correct |
1527 ms |
46532 KB |
Output is correct |
56 |
Correct |
1548 ms |
46492 KB |
Output is correct |
57 |
Correct |
20 ms |
44876 KB |
Output is correct |
58 |
Correct |
42 ms |
44964 KB |
Output is correct |
59 |
Correct |
1248 ms |
46444 KB |
Output is correct |
60 |
Correct |
1822 ms |
46716 KB |
Output is correct |
61 |
Correct |
1726 ms |
46728 KB |
Output is correct |
62 |
Correct |
1645 ms |
46636 KB |
Output is correct |
63 |
Correct |
1704 ms |
45856 KB |
Output is correct |
64 |
Correct |
1856 ms |
46100 KB |
Output is correct |
65 |
Correct |
1738 ms |
45672 KB |
Output is correct |
66 |
Correct |
1242 ms |
46628 KB |
Output is correct |
67 |
Correct |
1730 ms |
46756 KB |
Output is correct |
68 |
Correct |
1531 ms |
46632 KB |
Output is correct |
69 |
Correct |
1463 ms |
46588 KB |
Output is correct |
70 |
Correct |
1408 ms |
46660 KB |
Output is correct |
71 |
Correct |
1797 ms |
46704 KB |
Output is correct |