#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
vector<int> w, s;
vector<vector<long long>> when;
set<array<long long, 3>> res;
void init(int l, int N, vector<long long> t, vector<int> W, int X, int M, vector<int> S) {
n = N; m = M; x = X; w = W; s = S;
when = vector<vector<long long>>(m, vector<long long>(n));
when[0] = t;
for (int i = 1; i < m; i++) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (when[i - 1][a] != when[i - 1][b]) {
return when[i - 1][a] < when[i - 1][b];
} else {
return w[a] < w[b];
}
});
long long mx = 0;
for (int j = 0; j < n; j++) {
int b = order[j];
mx = max(mx, when[i - 1][b] + w[b] * 1LL * (s[i] - s[i - 1]));
when[i][b] = mx;
}
}
const long long inf = (long long) 1e18;
set<array<long long, 3>> st;
long long ft = 0;
set<pair<long long, long long>> id;
id.insert({inf, 0});
auto Update = [&](long long L, long long R, long long val) {
L = max(0LL, L);
if (L > R) {
return;
}
long long from = inf + 1, to = -1;
while (true) {
auto it = st.lower_bound({L, -1, -1});
if (it == st.end() || (*it)[0] > R) {
break;
}
long long l = (*it)[1], r = (*it)[2];
st.erase(it);
from = min(from, l);
to = max(to, r);
}
{
auto it = id.lower_bound({L, -1});
if (it != id.end()) {
long long pt = max(L, it->second);
if (pt >= it->second && pt <= it->first) {
from = min(from, pt);
}
}
}
{
auto it = id.lower_bound({R, -1});
if (it == id.end() || it->second > R) {
if (it != id.begin()) {
it = prev(it);
}
}
if (it != id.end()) {
long long pt = min(R, it->first);
if (pt >= it->second && pt <= it->first) {
to = max(to, pt);
}
}
}
if (from > to) {
return;
}
while (true) {
auto it = id.lower_bound({from, -1});
if (it == id.end() || it->second > to) {
break;
}
long long l = it->second, r = it->first;
id.erase(it);
if (l < from) {
id.insert({from - 1, l});
}
if (r > to) {
id.insert({r, to + 1});
}
}
st.insert({val, from, to});
};
for (int i = 1; i < m; i++) {
long long prv = ft;
ft += (s[i] - s[i - 1]) * 1LL * x;
vector<array<long long, 3>> ev;
for (int j = 0; j < n; j++) {
if (w[j] <= x) {
continue;
}
long long L = when[i][j] - w[j] * 1LL * (s[i] - s[i - 1]) + 1, R = when[i][j] - x * 1LL * (s[i] - s[i - 1]);
if (L > R) {
continue;
}
ev.push_back({L, R + 1, when[i][j]});
}
vector<long long> xs;
for (auto& p : ev) {
xs.push_back(p[0]);
xs.push_back(p[1]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int sz = (int) xs.size();
vector<vector<long long>> qs(sz);
for (auto& p : ev) {
{
int idx = (int) (lower_bound(xs.begin(), xs.end(), p[0]) - xs.begin());
qs[idx].push_back(p[2]);
}
{
int idx = (int) (lower_bound(xs.begin(), xs.end(), p[1]) - xs.begin());
qs[idx].push_back(~p[2]);
}
}
vector<array<long long, 3>> segs;
{
multiset<long long> st;
for (int j = 0; j + 1 < sz; j++) {
for (auto& v : qs[j]) {
if (v >= 0) {
st.insert(v);
} else {
st.erase(st.find(~v));
}
}
if (!st.empty()) {
segs.push_back({xs[j] - prv, xs[j + 1] - 1 - prv, *prev(st.end()) - ft});
}
}
}
reverse(segs.begin(), segs.end());
for (auto& p : segs) {
Update(p[0], p[1], p[2]);
}
}
for (auto& p : st) {
res.insert({p[2], p[1], p[0]});
}
return;
}
long long arrival_time(long long y) {
auto it = res.lower_bound({y, -1, -1});
if (it != res.end() && (*it)[1] <= y) {
y = (*it)[2];
}
return y + s.back() * 1LL * x;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
700 KB |
Output is correct |
9 |
Correct |
2 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
424 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
860 KB |
Output is correct |
10 |
Correct |
6 ms |
1116 KB |
Output is correct |
11 |
Correct |
7 ms |
1372 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
6 ms |
1116 KB |
Output is correct |
14 |
Correct |
6 ms |
860 KB |
Output is correct |
15 |
Correct |
5 ms |
564 KB |
Output is correct |
16 |
Correct |
5 ms |
348 KB |
Output is correct |
17 |
Correct |
4 ms |
584 KB |
Output is correct |
18 |
Correct |
5 ms |
604 KB |
Output is correct |
19 |
Correct |
5 ms |
604 KB |
Output is correct |
20 |
Correct |
5 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
344 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
4 ms |
348 KB |
Output is correct |
25 |
Correct |
3 ms |
348 KB |
Output is correct |
26 |
Correct |
3 ms |
348 KB |
Output is correct |
27 |
Correct |
3 ms |
348 KB |
Output is correct |
28 |
Correct |
3 ms |
344 KB |
Output is correct |
29 |
Correct |
3 ms |
348 KB |
Output is correct |
30 |
Correct |
3 ms |
348 KB |
Output is correct |
31 |
Correct |
3 ms |
344 KB |
Output is correct |
32 |
Correct |
7 ms |
1576 KB |
Output is correct |
33 |
Correct |
6 ms |
1628 KB |
Output is correct |
34 |
Correct |
7 ms |
1568 KB |
Output is correct |
35 |
Correct |
7 ms |
1628 KB |
Output is correct |
36 |
Correct |
6 ms |
1628 KB |
Output is correct |
37 |
Correct |
6 ms |
1624 KB |
Output is correct |
38 |
Correct |
1 ms |
344 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
5 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
860 KB |
Output is correct |
17 |
Correct |
6 ms |
1116 KB |
Output is correct |
18 |
Correct |
7 ms |
1372 KB |
Output is correct |
19 |
Correct |
6 ms |
860 KB |
Output is correct |
20 |
Correct |
6 ms |
1116 KB |
Output is correct |
21 |
Correct |
6 ms |
860 KB |
Output is correct |
22 |
Correct |
5 ms |
564 KB |
Output is correct |
23 |
Correct |
5 ms |
348 KB |
Output is correct |
24 |
Correct |
4 ms |
584 KB |
Output is correct |
25 |
Correct |
5 ms |
604 KB |
Output is correct |
26 |
Correct |
5 ms |
604 KB |
Output is correct |
27 |
Correct |
5 ms |
604 KB |
Output is correct |
28 |
Correct |
2 ms |
348 KB |
Output is correct |
29 |
Correct |
2 ms |
344 KB |
Output is correct |
30 |
Correct |
3 ms |
348 KB |
Output is correct |
31 |
Correct |
4 ms |
348 KB |
Output is correct |
32 |
Correct |
3 ms |
348 KB |
Output is correct |
33 |
Correct |
3 ms |
348 KB |
Output is correct |
34 |
Correct |
3 ms |
348 KB |
Output is correct |
35 |
Correct |
3 ms |
344 KB |
Output is correct |
36 |
Correct |
3 ms |
348 KB |
Output is correct |
37 |
Correct |
3 ms |
348 KB |
Output is correct |
38 |
Correct |
3 ms |
344 KB |
Output is correct |
39 |
Correct |
7 ms |
1576 KB |
Output is correct |
40 |
Correct |
6 ms |
1628 KB |
Output is correct |
41 |
Correct |
7 ms |
1568 KB |
Output is correct |
42 |
Correct |
7 ms |
1628 KB |
Output is correct |
43 |
Correct |
6 ms |
1628 KB |
Output is correct |
44 |
Correct |
6 ms |
1624 KB |
Output is correct |
45 |
Correct |
1 ms |
344 KB |
Output is correct |
46 |
Correct |
1 ms |
348 KB |
Output is correct |
47 |
Correct |
5 ms |
604 KB |
Output is correct |
48 |
Correct |
446 ms |
8788 KB |
Output is correct |
49 |
Correct |
412 ms |
9040 KB |
Output is correct |
50 |
Correct |
447 ms |
9556 KB |
Output is correct |
51 |
Correct |
413 ms |
8924 KB |
Output is correct |
52 |
Correct |
465 ms |
8844 KB |
Output is correct |
53 |
Correct |
407 ms |
9040 KB |
Output is correct |
54 |
Correct |
385 ms |
8784 KB |
Output is correct |
55 |
Correct |
417 ms |
8532 KB |
Output is correct |
56 |
Correct |
451 ms |
8784 KB |
Output is correct |
57 |
Correct |
417 ms |
8784 KB |
Output is correct |
58 |
Correct |
394 ms |
8744 KB |
Output is correct |
59 |
Correct |
409 ms |
8788 KB |
Output is correct |
60 |
Correct |
405 ms |
8768 KB |
Output is correct |
61 |
Correct |
395 ms |
8788 KB |
Output is correct |
62 |
Correct |
2 ms |
600 KB |
Output is correct |
63 |
Correct |
2 ms |
860 KB |
Output is correct |
64 |
Correct |
252 ms |
4512 KB |
Output is correct |
65 |
Correct |
230 ms |
4872 KB |
Output is correct |
66 |
Correct |
461 ms |
8784 KB |
Output is correct |
67 |
Correct |
423 ms |
8788 KB |
Output is correct |
68 |
Correct |
508 ms |
8844 KB |
Output is correct |
69 |
Correct |
1063 ms |
133456 KB |
Output is correct |
70 |
Correct |
1082 ms |
133456 KB |
Output is correct |
71 |
Correct |
1180 ms |
133344 KB |
Output is correct |
72 |
Correct |
1155 ms |
96796 KB |
Output is correct |
73 |
Correct |
1060 ms |
133604 KB |
Output is correct |
74 |
Correct |
1111 ms |
133456 KB |
Output is correct |
75 |
Correct |
44 ms |
8280 KB |
Output is correct |
76 |
Correct |
44 ms |
8284 KB |
Output is correct |
77 |
Correct |
39 ms |
8284 KB |
Output is correct |
78 |
Correct |
773 ms |
40020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
700 KB |
Output is correct |
21 |
Correct |
2 ms |
600 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
2 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
424 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
6 ms |
860 KB |
Output is correct |
28 |
Correct |
6 ms |
1116 KB |
Output is correct |
29 |
Correct |
7 ms |
1372 KB |
Output is correct |
30 |
Correct |
6 ms |
860 KB |
Output is correct |
31 |
Correct |
6 ms |
1116 KB |
Output is correct |
32 |
Correct |
6 ms |
860 KB |
Output is correct |
33 |
Correct |
5 ms |
564 KB |
Output is correct |
34 |
Correct |
5 ms |
348 KB |
Output is correct |
35 |
Correct |
4 ms |
584 KB |
Output is correct |
36 |
Correct |
5 ms |
604 KB |
Output is correct |
37 |
Correct |
5 ms |
604 KB |
Output is correct |
38 |
Correct |
5 ms |
604 KB |
Output is correct |
39 |
Correct |
2 ms |
348 KB |
Output is correct |
40 |
Correct |
2 ms |
344 KB |
Output is correct |
41 |
Correct |
3 ms |
348 KB |
Output is correct |
42 |
Correct |
4 ms |
348 KB |
Output is correct |
43 |
Correct |
3 ms |
348 KB |
Output is correct |
44 |
Correct |
3 ms |
348 KB |
Output is correct |
45 |
Correct |
3 ms |
348 KB |
Output is correct |
46 |
Correct |
3 ms |
344 KB |
Output is correct |
47 |
Correct |
3 ms |
348 KB |
Output is correct |
48 |
Correct |
3 ms |
348 KB |
Output is correct |
49 |
Correct |
3 ms |
344 KB |
Output is correct |
50 |
Correct |
7 ms |
1576 KB |
Output is correct |
51 |
Correct |
6 ms |
1628 KB |
Output is correct |
52 |
Correct |
7 ms |
1568 KB |
Output is correct |
53 |
Correct |
7 ms |
1628 KB |
Output is correct |
54 |
Correct |
6 ms |
1628 KB |
Output is correct |
55 |
Correct |
6 ms |
1624 KB |
Output is correct |
56 |
Correct |
1 ms |
344 KB |
Output is correct |
57 |
Correct |
1 ms |
348 KB |
Output is correct |
58 |
Correct |
5 ms |
604 KB |
Output is correct |
59 |
Correct |
446 ms |
8788 KB |
Output is correct |
60 |
Correct |
412 ms |
9040 KB |
Output is correct |
61 |
Correct |
447 ms |
9556 KB |
Output is correct |
62 |
Correct |
413 ms |
8924 KB |
Output is correct |
63 |
Correct |
465 ms |
8844 KB |
Output is correct |
64 |
Correct |
407 ms |
9040 KB |
Output is correct |
65 |
Correct |
385 ms |
8784 KB |
Output is correct |
66 |
Correct |
417 ms |
8532 KB |
Output is correct |
67 |
Correct |
451 ms |
8784 KB |
Output is correct |
68 |
Correct |
417 ms |
8784 KB |
Output is correct |
69 |
Correct |
394 ms |
8744 KB |
Output is correct |
70 |
Correct |
409 ms |
8788 KB |
Output is correct |
71 |
Correct |
405 ms |
8768 KB |
Output is correct |
72 |
Correct |
395 ms |
8788 KB |
Output is correct |
73 |
Correct |
2 ms |
600 KB |
Output is correct |
74 |
Correct |
2 ms |
860 KB |
Output is correct |
75 |
Correct |
252 ms |
4512 KB |
Output is correct |
76 |
Correct |
230 ms |
4872 KB |
Output is correct |
77 |
Correct |
461 ms |
8784 KB |
Output is correct |
78 |
Correct |
423 ms |
8788 KB |
Output is correct |
79 |
Correct |
508 ms |
8844 KB |
Output is correct |
80 |
Correct |
1063 ms |
133456 KB |
Output is correct |
81 |
Correct |
1082 ms |
133456 KB |
Output is correct |
82 |
Correct |
1180 ms |
133344 KB |
Output is correct |
83 |
Correct |
1155 ms |
96796 KB |
Output is correct |
84 |
Correct |
1060 ms |
133604 KB |
Output is correct |
85 |
Correct |
1111 ms |
133456 KB |
Output is correct |
86 |
Correct |
44 ms |
8280 KB |
Output is correct |
87 |
Correct |
44 ms |
8284 KB |
Output is correct |
88 |
Correct |
39 ms |
8284 KB |
Output is correct |
89 |
Correct |
773 ms |
40020 KB |
Output is correct |
90 |
Correct |
461 ms |
12064 KB |
Output is correct |
91 |
Correct |
605 ms |
43856 KB |
Output is correct |
92 |
Correct |
641 ms |
43720 KB |
Output is correct |
93 |
Correct |
630 ms |
44100 KB |
Output is correct |
94 |
Correct |
619 ms |
43628 KB |
Output is correct |
95 |
Correct |
620 ms |
43792 KB |
Output is correct |
96 |
Correct |
614 ms |
43980 KB |
Output is correct |
97 |
Correct |
447 ms |
11856 KB |
Output is correct |
98 |
Correct |
594 ms |
43344 KB |
Output is correct |
99 |
Correct |
637 ms |
44404 KB |
Output is correct |
100 |
Correct |
624 ms |
43724 KB |
Output is correct |
101 |
Correct |
596 ms |
43344 KB |
Output is correct |
102 |
Correct |
554 ms |
43468 KB |
Output is correct |
103 |
Correct |
568 ms |
43732 KB |
Output is correct |
104 |
Correct |
367 ms |
37464 KB |
Output is correct |
105 |
Correct |
426 ms |
42320 KB |
Output is correct |
106 |
Correct |
724 ms |
51788 KB |
Output is correct |
107 |
Correct |
656 ms |
51288 KB |
Output is correct |
108 |
Correct |
694 ms |
51540 KB |
Output is correct |
109 |
Correct |
657 ms |
51396 KB |
Output is correct |
110 |
Correct |
638 ms |
51512 KB |
Output is correct |
111 |
Correct |
1460 ms |
160684 KB |
Output is correct |
112 |
Correct |
1461 ms |
160756 KB |
Output is correct |
113 |
Correct |
1567 ms |
161620 KB |
Output is correct |
114 |
Correct |
1486 ms |
88768 KB |
Output is correct |
115 |
Correct |
1668 ms |
160856 KB |
Output is correct |
116 |
Correct |
1446 ms |
161976 KB |
Output is correct |
117 |
Correct |
248 ms |
47176 KB |
Output is correct |
118 |
Correct |
200 ms |
47188 KB |
Output is correct |
119 |
Correct |
195 ms |
45380 KB |
Output is correct |
120 |
Correct |
187 ms |
47296 KB |
Output is correct |
121 |
Correct |
218 ms |
48468 KB |
Output is correct |
122 |
Correct |
977 ms |
68944 KB |
Output is correct |
123 |
Correct |
1483 ms |
88644 KB |
Output is correct |
124 |
Correct |
1355 ms |
74324 KB |
Output is correct |
125 |
Correct |
1284 ms |
69432 KB |
Output is correct |