#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
static constexpr int mxN = 1000;
static map<arl2, ll> ans;
static int X, M;
static vt<int> S;
static vt<ll> T, times[mxN];
void init(int L, int N, vt<ll> _T, vt<int> W, int _X, int _M, vt<int> _S) {
X = _X;
S = _S;
M = _M;
T = _T;
vt<arl2> cur;
FOR(i, 0, N-1)
cur.push_back({T[i], W[i]});
FOR(i, 1, M-1) {
sort(all(cur));
vt<arl2> nxt;
for (auto [t, s] : cur) {
ll t2 = max(t + s * (S[i] - S[i-1]), size(times[i]) ? times[i].back() : 0ll);
nxt.push_back({t2, s});
times[i].push_back(t2);
if (i == M-1)
ans[{S[i], t2}] = t2;
}
cur = nxt;
}
ROF(i, M-2, 1)
for (auto t : times[i]) {
int ii = lower_bound(all(times[i]), t) - begin(times[i]) - 1;
if (ii < 0)
ans[{S[i], t}] = t + 1ll * X * (L - S[i]);
else {
int lo = i + 1, hi = M;
while (lo < hi) {
int mid = lo + hi >> 1;
if (times[mid][ii] >= t + 1ll * X * (S[mid] - S[i]))
hi = mid;
else
lo = mid + 1;
}
ans[{S[i], t}] = lo < M ? ans[{S[lo], times[lo][ii]}] : t + 1ll * X * (L - S[i]);
}
#ifdef DEBUG
cout << "ans(" << S[i] << ", " << t << ") = " << ans[{S[i], t}] << '\n';
#endif
}
sort(all(T));
}
ll arrival_time(ll Y) {
int i = lower_bound(all(T), Y) - begin(T) - 1;
if (i < 0)
return Y + 1ll * X * S[M-1];
int lo = 1, hi = M;
while (lo < hi) {
int mid = lo + hi >> 1;
if (times[mid][i] >= Y + 1ll * X * S[mid])
hi = mid;
else
lo = mid + 1;
}
return lo < M ? ans[{S[lo], times[lo][i]}] : Y + 1ll * X * S[M-1];
}
Compilation message
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:53:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = lo + hi >> 1;
| ~~~^~~~
overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = lo + hi >> 1;
| ~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
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 |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
472 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
344 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 |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
1116 KB |
Output is correct |
10 |
Correct |
3 ms |
1116 KB |
Output is correct |
11 |
Correct |
3 ms |
1116 KB |
Output is correct |
12 |
Correct |
3 ms |
1116 KB |
Output is correct |
13 |
Correct |
3 ms |
1112 KB |
Output is correct |
14 |
Correct |
3 ms |
1116 KB |
Output is correct |
15 |
Correct |
3 ms |
1112 KB |
Output is correct |
16 |
Correct |
3 ms |
1116 KB |
Output is correct |
17 |
Correct |
3 ms |
1116 KB |
Output is correct |
18 |
Correct |
3 ms |
1116 KB |
Output is correct |
19 |
Correct |
3 ms |
972 KB |
Output is correct |
20 |
Correct |
3 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
2 ms |
604 KB |
Output is correct |
23 |
Correct |
3 ms |
860 KB |
Output is correct |
24 |
Correct |
3 ms |
860 KB |
Output is correct |
25 |
Correct |
3 ms |
860 KB |
Output is correct |
26 |
Correct |
3 ms |
860 KB |
Output is correct |
27 |
Correct |
3 ms |
860 KB |
Output is correct |
28 |
Correct |
2 ms |
760 KB |
Output is correct |
29 |
Correct |
2 ms |
856 KB |
Output is correct |
30 |
Correct |
2 ms |
708 KB |
Output is correct |
31 |
Correct |
2 ms |
716 KB |
Output is correct |
32 |
Correct |
2 ms |
1116 KB |
Output is correct |
33 |
Correct |
3 ms |
1140 KB |
Output is correct |
34 |
Correct |
3 ms |
1112 KB |
Output is correct |
35 |
Correct |
3 ms |
1116 KB |
Output is correct |
36 |
Correct |
3 ms |
1048 KB |
Output is correct |
37 |
Correct |
3 ms |
1116 KB |
Output is correct |
38 |
Correct |
2 ms |
1116 KB |
Output is correct |
39 |
Correct |
2 ms |
1116 KB |
Output is correct |
40 |
Correct |
3 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
344 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 |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
472 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
1116 KB |
Output is correct |
17 |
Correct |
3 ms |
1116 KB |
Output is correct |
18 |
Correct |
3 ms |
1116 KB |
Output is correct |
19 |
Correct |
3 ms |
1116 KB |
Output is correct |
20 |
Correct |
3 ms |
1112 KB |
Output is correct |
21 |
Correct |
3 ms |
1116 KB |
Output is correct |
22 |
Correct |
3 ms |
1112 KB |
Output is correct |
23 |
Correct |
3 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
1116 KB |
Output is correct |
25 |
Correct |
3 ms |
1116 KB |
Output is correct |
26 |
Correct |
3 ms |
972 KB |
Output is correct |
27 |
Correct |
3 ms |
1116 KB |
Output is correct |
28 |
Correct |
2 ms |
604 KB |
Output is correct |
29 |
Correct |
2 ms |
604 KB |
Output is correct |
30 |
Correct |
3 ms |
860 KB |
Output is correct |
31 |
Correct |
3 ms |
860 KB |
Output is correct |
32 |
Correct |
3 ms |
860 KB |
Output is correct |
33 |
Correct |
3 ms |
860 KB |
Output is correct |
34 |
Correct |
3 ms |
860 KB |
Output is correct |
35 |
Correct |
2 ms |
760 KB |
Output is correct |
36 |
Correct |
2 ms |
856 KB |
Output is correct |
37 |
Correct |
2 ms |
708 KB |
Output is correct |
38 |
Correct |
2 ms |
716 KB |
Output is correct |
39 |
Correct |
2 ms |
1116 KB |
Output is correct |
40 |
Correct |
3 ms |
1140 KB |
Output is correct |
41 |
Correct |
3 ms |
1112 KB |
Output is correct |
42 |
Correct |
3 ms |
1116 KB |
Output is correct |
43 |
Correct |
3 ms |
1048 KB |
Output is correct |
44 |
Correct |
3 ms |
1116 KB |
Output is correct |
45 |
Correct |
2 ms |
1116 KB |
Output is correct |
46 |
Correct |
2 ms |
1116 KB |
Output is correct |
47 |
Correct |
3 ms |
1116 KB |
Output is correct |
48 |
Correct |
472 ms |
67980 KB |
Output is correct |
49 |
Correct |
491 ms |
68300 KB |
Output is correct |
50 |
Correct |
518 ms |
69952 KB |
Output is correct |
51 |
Correct |
499 ms |
68308 KB |
Output is correct |
52 |
Correct |
497 ms |
68436 KB |
Output is correct |
53 |
Correct |
503 ms |
68668 KB |
Output is correct |
54 |
Correct |
509 ms |
68536 KB |
Output is correct |
55 |
Correct |
327 ms |
46856 KB |
Output is correct |
56 |
Correct |
428 ms |
68244 KB |
Output is correct |
57 |
Correct |
412 ms |
64340 KB |
Output is correct |
58 |
Correct |
439 ms |
68692 KB |
Output is correct |
59 |
Correct |
429 ms |
68048 KB |
Output is correct |
60 |
Correct |
415 ms |
67924 KB |
Output is correct |
61 |
Correct |
432 ms |
68676 KB |
Output is correct |
62 |
Correct |
3 ms |
604 KB |
Output is correct |
63 |
Correct |
2 ms |
724 KB |
Output is correct |
64 |
Correct |
205 ms |
33896 KB |
Output is correct |
65 |
Correct |
198 ms |
33480 KB |
Output is correct |
66 |
Correct |
387 ms |
65364 KB |
Output is correct |
67 |
Correct |
390 ms |
66860 KB |
Output is correct |
68 |
Correct |
386 ms |
66644 KB |
Output is correct |
69 |
Correct |
331 ms |
71260 KB |
Output is correct |
70 |
Correct |
327 ms |
71252 KB |
Output is correct |
71 |
Correct |
330 ms |
71252 KB |
Output is correct |
72 |
Correct |
514 ms |
71216 KB |
Output is correct |
73 |
Correct |
327 ms |
71096 KB |
Output is correct |
74 |
Correct |
317 ms |
71232 KB |
Output is correct |
75 |
Correct |
285 ms |
65364 KB |
Output is correct |
76 |
Correct |
279 ms |
65396 KB |
Output is correct |
77 |
Correct |
293 ms |
66100 KB |
Output is correct |
78 |
Correct |
408 ms |
70996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
344 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 |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
472 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
600 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
2 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
3 ms |
1116 KB |
Output is correct |
28 |
Correct |
3 ms |
1116 KB |
Output is correct |
29 |
Correct |
3 ms |
1116 KB |
Output is correct |
30 |
Correct |
3 ms |
1116 KB |
Output is correct |
31 |
Correct |
3 ms |
1112 KB |
Output is correct |
32 |
Correct |
3 ms |
1116 KB |
Output is correct |
33 |
Correct |
3 ms |
1112 KB |
Output is correct |
34 |
Correct |
3 ms |
1116 KB |
Output is correct |
35 |
Correct |
3 ms |
1116 KB |
Output is correct |
36 |
Correct |
3 ms |
1116 KB |
Output is correct |
37 |
Correct |
3 ms |
972 KB |
Output is correct |
38 |
Correct |
3 ms |
1116 KB |
Output is correct |
39 |
Correct |
2 ms |
604 KB |
Output is correct |
40 |
Correct |
2 ms |
604 KB |
Output is correct |
41 |
Correct |
3 ms |
860 KB |
Output is correct |
42 |
Correct |
3 ms |
860 KB |
Output is correct |
43 |
Correct |
3 ms |
860 KB |
Output is correct |
44 |
Correct |
3 ms |
860 KB |
Output is correct |
45 |
Correct |
3 ms |
860 KB |
Output is correct |
46 |
Correct |
2 ms |
760 KB |
Output is correct |
47 |
Correct |
2 ms |
856 KB |
Output is correct |
48 |
Correct |
2 ms |
708 KB |
Output is correct |
49 |
Correct |
2 ms |
716 KB |
Output is correct |
50 |
Correct |
2 ms |
1116 KB |
Output is correct |
51 |
Correct |
3 ms |
1140 KB |
Output is correct |
52 |
Correct |
3 ms |
1112 KB |
Output is correct |
53 |
Correct |
3 ms |
1116 KB |
Output is correct |
54 |
Correct |
3 ms |
1048 KB |
Output is correct |
55 |
Correct |
3 ms |
1116 KB |
Output is correct |
56 |
Correct |
2 ms |
1116 KB |
Output is correct |
57 |
Correct |
2 ms |
1116 KB |
Output is correct |
58 |
Correct |
3 ms |
1116 KB |
Output is correct |
59 |
Correct |
472 ms |
67980 KB |
Output is correct |
60 |
Correct |
491 ms |
68300 KB |
Output is correct |
61 |
Correct |
518 ms |
69952 KB |
Output is correct |
62 |
Correct |
499 ms |
68308 KB |
Output is correct |
63 |
Correct |
497 ms |
68436 KB |
Output is correct |
64 |
Correct |
503 ms |
68668 KB |
Output is correct |
65 |
Correct |
509 ms |
68536 KB |
Output is correct |
66 |
Correct |
327 ms |
46856 KB |
Output is correct |
67 |
Correct |
428 ms |
68244 KB |
Output is correct |
68 |
Correct |
412 ms |
64340 KB |
Output is correct |
69 |
Correct |
439 ms |
68692 KB |
Output is correct |
70 |
Correct |
429 ms |
68048 KB |
Output is correct |
71 |
Correct |
415 ms |
67924 KB |
Output is correct |
72 |
Correct |
432 ms |
68676 KB |
Output is correct |
73 |
Correct |
3 ms |
604 KB |
Output is correct |
74 |
Correct |
2 ms |
724 KB |
Output is correct |
75 |
Correct |
205 ms |
33896 KB |
Output is correct |
76 |
Correct |
198 ms |
33480 KB |
Output is correct |
77 |
Correct |
387 ms |
65364 KB |
Output is correct |
78 |
Correct |
390 ms |
66860 KB |
Output is correct |
79 |
Correct |
386 ms |
66644 KB |
Output is correct |
80 |
Correct |
331 ms |
71260 KB |
Output is correct |
81 |
Correct |
327 ms |
71252 KB |
Output is correct |
82 |
Correct |
330 ms |
71252 KB |
Output is correct |
83 |
Correct |
514 ms |
71216 KB |
Output is correct |
84 |
Correct |
327 ms |
71096 KB |
Output is correct |
85 |
Correct |
317 ms |
71232 KB |
Output is correct |
86 |
Correct |
285 ms |
65364 KB |
Output is correct |
87 |
Correct |
279 ms |
65396 KB |
Output is correct |
88 |
Correct |
293 ms |
66100 KB |
Output is correct |
89 |
Correct |
408 ms |
70996 KB |
Output is correct |
90 |
Correct |
538 ms |
70460 KB |
Output is correct |
91 |
Correct |
1014 ms |
103104 KB |
Output is correct |
92 |
Correct |
1089 ms |
103992 KB |
Output is correct |
93 |
Correct |
1064 ms |
103400 KB |
Output is correct |
94 |
Correct |
1074 ms |
103508 KB |
Output is correct |
95 |
Correct |
1053 ms |
103304 KB |
Output is correct |
96 |
Correct |
1027 ms |
103656 KB |
Output is correct |
97 |
Correct |
418 ms |
50764 KB |
Output is correct |
98 |
Correct |
1076 ms |
102612 KB |
Output is correct |
99 |
Correct |
1067 ms |
99924 KB |
Output is correct |
100 |
Correct |
1111 ms |
102804 KB |
Output is correct |
101 |
Correct |
1122 ms |
102032 KB |
Output is correct |
102 |
Correct |
1074 ms |
102600 KB |
Output is correct |
103 |
Correct |
1090 ms |
102996 KB |
Output is correct |
104 |
Correct |
537 ms |
66388 KB |
Output is correct |
105 |
Correct |
556 ms |
69968 KB |
Output is correct |
106 |
Correct |
792 ms |
109400 KB |
Output is correct |
107 |
Correct |
810 ms |
107168 KB |
Output is correct |
108 |
Correct |
822 ms |
108524 KB |
Output is correct |
109 |
Correct |
801 ms |
107328 KB |
Output is correct |
110 |
Correct |
815 ms |
108740 KB |
Output is correct |
111 |
Correct |
631 ms |
106420 KB |
Output is correct |
112 |
Correct |
636 ms |
106340 KB |
Output is correct |
113 |
Correct |
1268 ms |
107224 KB |
Output is correct |
114 |
Correct |
2106 ms |
108540 KB |
Output is correct |
115 |
Correct |
1149 ms |
106720 KB |
Output is correct |
116 |
Correct |
697 ms |
107264 KB |
Output is correct |
117 |
Correct |
566 ms |
102888 KB |
Output is correct |
118 |
Correct |
570 ms |
104212 KB |
Output is correct |
119 |
Correct |
558 ms |
102884 KB |
Output is correct |
120 |
Correct |
569 ms |
105148 KB |
Output is correct |
121 |
Correct |
570 ms |
105308 KB |
Output is correct |
122 |
Correct |
1399 ms |
100420 KB |
Output is correct |
123 |
Correct |
2235 ms |
108372 KB |
Output is correct |
124 |
Correct |
2123 ms |
108376 KB |
Output is correct |
125 |
Correct |
2319 ms |
108264 KB |
Output is correct |