#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, 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, -INF});
if(r & 1)
upd(--r, {v, -INF});
}
pull(tl); pull(tr);
}
void edt2(int l, int r, 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++, {INF, v});
if(r & 1)
upd(--r, {INF, 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), tree[0].edt2(i, i + 1, i);
for(const auto &[a, b] : arr) {
if(a < b)
tree[0].edt2(a, min(b + 1, a + k), b);
else
tree[0].edt(max(b, a - k + 1), a + 1, b);
}
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);
tree[i].edt2(j, j + 1, 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--)
if(!in(t, tree[i].que(owo.first, owo.second + 1)))
owo = tree[i].que(owo.first, owo.second + 1), res |= 1 << i;
cout << res + 1 << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
44932 KB |
Output is correct |
2 |
Correct |
23 ms |
44884 KB |
Output is correct |
3 |
Correct |
22 ms |
44944 KB |
Output is correct |
4 |
Correct |
21 ms |
44920 KB |
Output is correct |
5 |
Correct |
22 ms |
44908 KB |
Output is correct |
6 |
Correct |
22 ms |
44948 KB |
Output is correct |
7 |
Correct |
22 ms |
44884 KB |
Output is correct |
8 |
Correct |
22 ms |
44876 KB |
Output is correct |
9 |
Correct |
22 ms |
44824 KB |
Output is correct |
10 |
Correct |
18 ms |
44856 KB |
Output is correct |
11 |
Correct |
25 ms |
44876 KB |
Output is correct |
12 |
Correct |
22 ms |
44876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
44932 KB |
Output is correct |
2 |
Correct |
23 ms |
44884 KB |
Output is correct |
3 |
Correct |
22 ms |
44944 KB |
Output is correct |
4 |
Correct |
21 ms |
44920 KB |
Output is correct |
5 |
Correct |
22 ms |
44908 KB |
Output is correct |
6 |
Correct |
22 ms |
44948 KB |
Output is correct |
7 |
Correct |
22 ms |
44884 KB |
Output is correct |
8 |
Correct |
22 ms |
44876 KB |
Output is correct |
9 |
Correct |
22 ms |
44824 KB |
Output is correct |
10 |
Correct |
18 ms |
44856 KB |
Output is correct |
11 |
Correct |
25 ms |
44876 KB |
Output is correct |
12 |
Correct |
22 ms |
44876 KB |
Output is correct |
13 |
Correct |
48 ms |
44940 KB |
Output is correct |
14 |
Correct |
46 ms |
44900 KB |
Output is correct |
15 |
Correct |
38 ms |
44876 KB |
Output is correct |
16 |
Correct |
38 ms |
44948 KB |
Output is correct |
17 |
Correct |
44 ms |
44912 KB |
Output is correct |
18 |
Correct |
45 ms |
44928 KB |
Output is correct |
19 |
Correct |
43 ms |
44960 KB |
Output is correct |
20 |
Correct |
44 ms |
44952 KB |
Output is correct |
21 |
Correct |
38 ms |
44940 KB |
Output is correct |
22 |
Correct |
45 ms |
44936 KB |
Output is correct |
23 |
Correct |
46 ms |
44948 KB |
Output is correct |
24 |
Correct |
43 ms |
44832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1490 ms |
45516 KB |
Output is correct |
2 |
Correct |
1467 ms |
45516 KB |
Output is correct |
3 |
Correct |
1511 ms |
45632 KB |
Output is correct |
4 |
Correct |
1498 ms |
45516 KB |
Output is correct |
5 |
Correct |
1493 ms |
46412 KB |
Output is correct |
6 |
Correct |
1489 ms |
46404 KB |
Output is correct |
7 |
Correct |
1465 ms |
46412 KB |
Output is correct |
8 |
Correct |
1422 ms |
45644 KB |
Output is correct |
9 |
Correct |
1434 ms |
45644 KB |
Output is correct |
10 |
Correct |
1484 ms |
46412 KB |
Output is correct |
11 |
Correct |
1495 ms |
46412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1990 ms |
45688 KB |
Output is correct |
2 |
Correct |
1508 ms |
46632 KB |
Output is correct |
3 |
Correct |
1991 ms |
45976 KB |
Output is correct |
4 |
Correct |
1795 ms |
46500 KB |
Output is correct |
5 |
Correct |
1750 ms |
46500 KB |
Output is correct |
6 |
Correct |
1730 ms |
46496 KB |
Output is correct |
7 |
Correct |
1834 ms |
46644 KB |
Output is correct |
8 |
Execution timed out |
2017 ms |
46632 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1549 ms |
46624 KB |
Output is correct |
2 |
Execution timed out |
2101 ms |
45916 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
44932 KB |
Output is correct |
2 |
Correct |
23 ms |
44884 KB |
Output is correct |
3 |
Correct |
22 ms |
44944 KB |
Output is correct |
4 |
Correct |
21 ms |
44920 KB |
Output is correct |
5 |
Correct |
22 ms |
44908 KB |
Output is correct |
6 |
Correct |
22 ms |
44948 KB |
Output is correct |
7 |
Correct |
22 ms |
44884 KB |
Output is correct |
8 |
Correct |
22 ms |
44876 KB |
Output is correct |
9 |
Correct |
22 ms |
44824 KB |
Output is correct |
10 |
Correct |
18 ms |
44856 KB |
Output is correct |
11 |
Correct |
25 ms |
44876 KB |
Output is correct |
12 |
Correct |
22 ms |
44876 KB |
Output is correct |
13 |
Correct |
48 ms |
44940 KB |
Output is correct |
14 |
Correct |
46 ms |
44900 KB |
Output is correct |
15 |
Correct |
38 ms |
44876 KB |
Output is correct |
16 |
Correct |
38 ms |
44948 KB |
Output is correct |
17 |
Correct |
44 ms |
44912 KB |
Output is correct |
18 |
Correct |
45 ms |
44928 KB |
Output is correct |
19 |
Correct |
43 ms |
44960 KB |
Output is correct |
20 |
Correct |
44 ms |
44952 KB |
Output is correct |
21 |
Correct |
38 ms |
44940 KB |
Output is correct |
22 |
Correct |
45 ms |
44936 KB |
Output is correct |
23 |
Correct |
46 ms |
44948 KB |
Output is correct |
24 |
Correct |
43 ms |
44832 KB |
Output is correct |
25 |
Correct |
1490 ms |
45516 KB |
Output is correct |
26 |
Correct |
1467 ms |
45516 KB |
Output is correct |
27 |
Correct |
1511 ms |
45632 KB |
Output is correct |
28 |
Correct |
1498 ms |
45516 KB |
Output is correct |
29 |
Correct |
1493 ms |
46412 KB |
Output is correct |
30 |
Correct |
1489 ms |
46404 KB |
Output is correct |
31 |
Correct |
1465 ms |
46412 KB |
Output is correct |
32 |
Correct |
1422 ms |
45644 KB |
Output is correct |
33 |
Correct |
1434 ms |
45644 KB |
Output is correct |
34 |
Correct |
1484 ms |
46412 KB |
Output is correct |
35 |
Correct |
1495 ms |
46412 KB |
Output is correct |
36 |
Correct |
1990 ms |
45688 KB |
Output is correct |
37 |
Correct |
1508 ms |
46632 KB |
Output is correct |
38 |
Correct |
1991 ms |
45976 KB |
Output is correct |
39 |
Correct |
1795 ms |
46500 KB |
Output is correct |
40 |
Correct |
1750 ms |
46500 KB |
Output is correct |
41 |
Correct |
1730 ms |
46496 KB |
Output is correct |
42 |
Correct |
1834 ms |
46644 KB |
Output is correct |
43 |
Execution timed out |
2017 ms |
46632 KB |
Time limit exceeded |
44 |
Halted |
0 ms |
0 KB |
- |