# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
528613 |
2022-02-20T18:50:43 Z |
WLZ |
Railway Trip 2 (JOI22_ho_t4) |
C++14 |
|
1774 ms |
190800 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct node {
int l, r, mn, mx;
node *left, *right;
};
node *build(int l, int r, const vector<int> &_mn, const vector<int> &_mx) {
if (l == r) return new node{l, r, _mn[l], _mx[l], nullptr, nullptr};
node *left = build(l, (l + r) / 2, _mn, _mx), *right = build((l + r) / 2 + 1, r, _mn, _mx);
return new node{l, r, min(left->mn, right->mn), max(left->mx, right->mx), left, right};
}
pair<int, int> query(node *cur, int l, int r) {
if (cur->l > r || cur->r < l) return {INF, -INF};
if (l <= cur->l && cur->r <= r) return {cur->mn, cur->mx};
auto left = query(cur->left, l, r), right = query(cur->right, l, r);
return {min(left.first, right.first), max(left.second, right.second)};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, max_log;
cin >> n >> k;
max_log = ceil(log2(n)) + 1;
int m;
cin >> m;
vector< vector<int> > mx_diff(n + 1), mn_diff(n + 1);
while (m--) {
int a, b;
cin >> a >> b;
if (a < b) {
mx_diff[a].push_back(b);
if (min(a + k, b + 1) <= n) mx_diff[min(a + k, b + 1)].push_back(-b);
} else {
mn_diff[a].push_back(b);
if (max(a - k, b - 1) >= 1) mn_diff[max(a - k, b - 1)].push_back(-b);
}
}
vector<int> mn(n + 1), mx(n + 1);
iota(mn.begin(), mn.end(), 0);
iota(mx.begin(), mx.end(), 0);
map<int, int> mp;
for (int i = 1; i <= n; i++) {
for (auto &x : mx_diff[i]) {
if (x > 0) mp[x]++;
else if (--mp[-x] == 0) mp.erase(-x);
}
if (!mp.empty()) mx[i] = mp.rbegin()->first;
}
mp.clear();
for (int i = n; i >= 1; i--) {
for (auto &x : mn_diff[i]) {
if (x > 0) mp[x]++;
else if (--mp[-x] == 0) mp.erase(-x);
}
if (!mp.empty()) mn[i] = mp.begin()->first;
}
vector<node*> up(max_log + 1);
up[0] = build(1, n, mn, mx);
for (int i = 1; i <= max_log; i++) {
for (int j = 1; j <= n; j++) {
tie(mn[j], mx[j]) = query(up[i - 1], mn[j], mx[j]);
}
up[i] = build(1, n, mn, mx);
}
int q;
cin >> q;
while (q--) {
int s, t;
cin >> s >> t;
int l, r;
tie(l, r) = query(up[max_log], s, s);
if (t < l || t > r) {
cout << -1 << '\n';
continue;
}
l = s, r = s;
int ans = 0;
for (int i = max_log; i >= 0; i--) {
int nl, nr;
tie(nl, nr) = query(up[i], l, r);
if (t < nl || t > nr) {
l = nl, r = nr;
ans += (1 << i);
}
}
cout << ans + 1 << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
648 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
592 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
648 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
592 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
13 |
Correct |
12 ms |
2920 KB |
Output is correct |
14 |
Correct |
12 ms |
2892 KB |
Output is correct |
15 |
Correct |
5 ms |
2876 KB |
Output is correct |
16 |
Correct |
8 ms |
2892 KB |
Output is correct |
17 |
Correct |
10 ms |
2992 KB |
Output is correct |
18 |
Correct |
7 ms |
2892 KB |
Output is correct |
19 |
Correct |
9 ms |
2764 KB |
Output is correct |
20 |
Correct |
7 ms |
2892 KB |
Output is correct |
21 |
Correct |
4 ms |
2892 KB |
Output is correct |
22 |
Correct |
10 ms |
2892 KB |
Output is correct |
23 |
Correct |
9 ms |
2892 KB |
Output is correct |
24 |
Correct |
8 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
532 ms |
187076 KB |
Output is correct |
2 |
Correct |
546 ms |
187068 KB |
Output is correct |
3 |
Correct |
575 ms |
187348 KB |
Output is correct |
4 |
Correct |
525 ms |
187024 KB |
Output is correct |
5 |
Correct |
312 ms |
189892 KB |
Output is correct |
6 |
Correct |
611 ms |
190460 KB |
Output is correct |
7 |
Correct |
213 ms |
190492 KB |
Output is correct |
8 |
Correct |
238 ms |
186256 KB |
Output is correct |
9 |
Correct |
218 ms |
188216 KB |
Output is correct |
10 |
Correct |
536 ms |
189968 KB |
Output is correct |
11 |
Correct |
496 ms |
189980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1087 ms |
189208 KB |
Output is correct |
2 |
Correct |
516 ms |
190060 KB |
Output is correct |
3 |
Correct |
1240 ms |
190800 KB |
Output is correct |
4 |
Correct |
558 ms |
190496 KB |
Output is correct |
5 |
Correct |
579 ms |
188048 KB |
Output is correct |
6 |
Correct |
552 ms |
189976 KB |
Output is correct |
7 |
Correct |
1140 ms |
190128 KB |
Output is correct |
8 |
Correct |
1107 ms |
190048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
577 ms |
188448 KB |
Output is correct |
2 |
Correct |
1774 ms |
187688 KB |
Output is correct |
3 |
Correct |
1628 ms |
186072 KB |
Output is correct |
4 |
Correct |
1447 ms |
185036 KB |
Output is correct |
5 |
Correct |
1100 ms |
185008 KB |
Output is correct |
6 |
Correct |
1074 ms |
184432 KB |
Output is correct |
7 |
Correct |
758 ms |
187508 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
8 ms |
2892 KB |
Output is correct |
10 |
Correct |
562 ms |
188304 KB |
Output is correct |
11 |
Correct |
699 ms |
188484 KB |
Output is correct |
12 |
Correct |
785 ms |
186564 KB |
Output is correct |
13 |
Correct |
799 ms |
188460 KB |
Output is correct |
14 |
Correct |
1 ms |
588 KB |
Output is correct |
15 |
Correct |
11 ms |
2892 KB |
Output is correct |
16 |
Correct |
577 ms |
188464 KB |
Output is correct |
17 |
Correct |
1612 ms |
188728 KB |
Output is correct |
18 |
Correct |
1332 ms |
188680 KB |
Output is correct |
19 |
Correct |
1144 ms |
188672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
648 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
592 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
13 |
Correct |
12 ms |
2920 KB |
Output is correct |
14 |
Correct |
12 ms |
2892 KB |
Output is correct |
15 |
Correct |
5 ms |
2876 KB |
Output is correct |
16 |
Correct |
8 ms |
2892 KB |
Output is correct |
17 |
Correct |
10 ms |
2992 KB |
Output is correct |
18 |
Correct |
7 ms |
2892 KB |
Output is correct |
19 |
Correct |
9 ms |
2764 KB |
Output is correct |
20 |
Correct |
7 ms |
2892 KB |
Output is correct |
21 |
Correct |
4 ms |
2892 KB |
Output is correct |
22 |
Correct |
10 ms |
2892 KB |
Output is correct |
23 |
Correct |
9 ms |
2892 KB |
Output is correct |
24 |
Correct |
8 ms |
2892 KB |
Output is correct |
25 |
Correct |
532 ms |
187076 KB |
Output is correct |
26 |
Correct |
546 ms |
187068 KB |
Output is correct |
27 |
Correct |
575 ms |
187348 KB |
Output is correct |
28 |
Correct |
525 ms |
187024 KB |
Output is correct |
29 |
Correct |
312 ms |
189892 KB |
Output is correct |
30 |
Correct |
611 ms |
190460 KB |
Output is correct |
31 |
Correct |
213 ms |
190492 KB |
Output is correct |
32 |
Correct |
238 ms |
186256 KB |
Output is correct |
33 |
Correct |
218 ms |
188216 KB |
Output is correct |
34 |
Correct |
536 ms |
189968 KB |
Output is correct |
35 |
Correct |
496 ms |
189980 KB |
Output is correct |
36 |
Correct |
1087 ms |
189208 KB |
Output is correct |
37 |
Correct |
516 ms |
190060 KB |
Output is correct |
38 |
Correct |
1240 ms |
190800 KB |
Output is correct |
39 |
Correct |
558 ms |
190496 KB |
Output is correct |
40 |
Correct |
579 ms |
188048 KB |
Output is correct |
41 |
Correct |
552 ms |
189976 KB |
Output is correct |
42 |
Correct |
1140 ms |
190128 KB |
Output is correct |
43 |
Correct |
1107 ms |
190048 KB |
Output is correct |
44 |
Correct |
577 ms |
188448 KB |
Output is correct |
45 |
Correct |
1774 ms |
187688 KB |
Output is correct |
46 |
Correct |
1628 ms |
186072 KB |
Output is correct |
47 |
Correct |
1447 ms |
185036 KB |
Output is correct |
48 |
Correct |
1100 ms |
185008 KB |
Output is correct |
49 |
Correct |
1074 ms |
184432 KB |
Output is correct |
50 |
Correct |
758 ms |
187508 KB |
Output is correct |
51 |
Correct |
1 ms |
588 KB |
Output is correct |
52 |
Correct |
8 ms |
2892 KB |
Output is correct |
53 |
Correct |
562 ms |
188304 KB |
Output is correct |
54 |
Correct |
699 ms |
188484 KB |
Output is correct |
55 |
Correct |
785 ms |
186564 KB |
Output is correct |
56 |
Correct |
799 ms |
188460 KB |
Output is correct |
57 |
Correct |
1 ms |
588 KB |
Output is correct |
58 |
Correct |
11 ms |
2892 KB |
Output is correct |
59 |
Correct |
577 ms |
188464 KB |
Output is correct |
60 |
Correct |
1612 ms |
188728 KB |
Output is correct |
61 |
Correct |
1332 ms |
188680 KB |
Output is correct |
62 |
Correct |
1144 ms |
188672 KB |
Output is correct |
63 |
Correct |
1360 ms |
187428 KB |
Output is correct |
64 |
Correct |
1584 ms |
187460 KB |
Output is correct |
65 |
Correct |
1361 ms |
187568 KB |
Output is correct |
66 |
Correct |
315 ms |
189936 KB |
Output is correct |
67 |
Correct |
1251 ms |
190796 KB |
Output is correct |
68 |
Correct |
928 ms |
187704 KB |
Output is correct |
69 |
Correct |
603 ms |
189792 KB |
Output is correct |
70 |
Correct |
873 ms |
189956 KB |
Output is correct |
71 |
Correct |
1525 ms |
190148 KB |
Output is correct |