#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int l, n, x, m;
vector<ll> t;
vector<int> w, s;
ll est[1010][1010], arr[1010][1010];
pll range[1010][1010];
struct seg {
int sz;
vector<ll> vals;
ll tree[8080], lazy[8080];
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = -1;
lazy[v] = -1;
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
lazy[v] = -1;
}
void propagate(int v, int st, int ed) {
tree[v] = max(tree[v], lazy[v]);
if (st != ed) {
lazy[2 * v] = max(lazy[2 * v], lazy[v]);
lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
}
}
void update(int v, int st, int ed, int lt, int rt, ll val) {
propagate(v, st, ed);
if (lt > ed || rt < st) return;
if (lt <= st && ed <= rt) {
lazy[v] = max(lazy[v], val);
propagate(v, st, ed);
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, lt, rt, val);
update(2 * v + 1, mid + 1, ed, lt, rt, val);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
ll get(int v, int st, int ed, int idx) {
propagate(v, st, ed);
if (st > idx || ed < idx) return -1;
if (st == idx && ed == idx) return tree[v];
int mid = (st + ed) / 2;
return max(get(2 * v, st, mid, idx), get(2 * v + 1, mid + 1, ed, idx));
}
} sg[1010];
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L; n = N; t = T; w = W; x = X; m = M; s = S;
for (int i = 0; i < n; i++) arr[0][i] = t[i];
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) est[j][i] = arr[j - 1][i] + (ll)w[i] * (s[j] - s[j - 1]);
vector<pll> tlist;
for (int i = 0; i < n; i++) tlist.push_back({arr[j - 1][i], i});
sort(tlist.begin(), tlist.end());
ll last = 0, p = 0;
for (int i = 0; i < n; i++) {
while (tlist[p].first < tlist[i].first) {
last = max(last, est[j][tlist[p].second]);
p++;
}
arr[j][tlist[i].second] = max(last, est[j][tlist[i].second]);
}
}
for (int j = 0; j < m - 1; j++) {
for (int i = 0; i < n; i++) {
if (w[i] > x) {
range[j][i] = {arr[j][i] + 1, arr[j][i] + (ll)(w[i] - x) * (s[j + 1] - s[j])};
sg[j].vals.push_back(range[j][i].first);
sg[j].vals.push_back(range[j][i].second);
}
}
sort(sg[j].vals.begin(), sg[j].vals.end());
sg[j].vals.erase(unique(sg[j].vals.begin(), sg[j].vals.end()), sg[j].vals.end());
sg[j].sz = sg[j].vals.size();
sg[j].init(1, 0, sg[j].sz);
for (int i = 0; i < n; i++) {
if (w[i] > x) {
int s = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].first)
- sg[j].vals.begin() + 1;
int e = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].second)
- sg[j].vals.begin() + 1;
sg[j].update(1, 0, sg[j].sz, s, e - 1, arr[j + 1][i]);
}
}
}
return;
}
ll arrival_time(ll Y) {
ll y = Y;
for (int j = 0; j < m - 1; j++) {
int idx = upper_bound(sg[j].vals.begin(), sg[j].vals.end(), y)
- sg[j].vals.begin();
ll next = sg[j].get(1, 0, sg[j].sz, idx);
if (next >= 0) y = next;
else y = y + (ll)x * (s[j + 1] - s[j]);
//cout << y << "\n";
}
return y;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
133724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
135664 KB |
Output is correct |
2 |
Correct |
14 ms |
137820 KB |
Output is correct |
3 |
Correct |
14 ms |
137816 KB |
Output is correct |
4 |
Correct |
13 ms |
137820 KB |
Output is correct |
5 |
Correct |
15 ms |
137816 KB |
Output is correct |
6 |
Correct |
19 ms |
148060 KB |
Output is correct |
7 |
Correct |
25 ms |
158492 KB |
Output is correct |
8 |
Correct |
27 ms |
159068 KB |
Output is correct |
9 |
Correct |
29 ms |
159064 KB |
Output is correct |
10 |
Correct |
27 ms |
159068 KB |
Output is correct |
11 |
Correct |
18 ms |
147056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
133724 KB |
Output is correct |
2 |
Correct |
13 ms |
133676 KB |
Output is correct |
3 |
Correct |
12 ms |
133724 KB |
Output is correct |
4 |
Correct |
14 ms |
133724 KB |
Output is correct |
5 |
Correct |
13 ms |
133804 KB |
Output is correct |
6 |
Correct |
15 ms |
133724 KB |
Output is correct |
7 |
Correct |
15 ms |
133980 KB |
Output is correct |
8 |
Correct |
14 ms |
133792 KB |
Output is correct |
9 |
Correct |
14 ms |
133764 KB |
Output is correct |
10 |
Correct |
13 ms |
133724 KB |
Output is correct |
11 |
Correct |
15 ms |
133956 KB |
Output is correct |
12 |
Correct |
15 ms |
133980 KB |
Output is correct |
13 |
Correct |
14 ms |
133736 KB |
Output is correct |
14 |
Correct |
14 ms |
133724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
133724 KB |
Output is correct |
2 |
Correct |
13 ms |
135664 KB |
Output is correct |
3 |
Correct |
14 ms |
137820 KB |
Output is correct |
4 |
Correct |
14 ms |
137816 KB |
Output is correct |
5 |
Correct |
13 ms |
137820 KB |
Output is correct |
6 |
Correct |
13 ms |
133724 KB |
Output is correct |
7 |
Correct |
13 ms |
133676 KB |
Output is correct |
8 |
Correct |
12 ms |
133724 KB |
Output is correct |
9 |
Correct |
16 ms |
138124 KB |
Output is correct |
10 |
Correct |
18 ms |
138076 KB |
Output is correct |
11 |
Correct |
15 ms |
138076 KB |
Output is correct |
12 |
Correct |
16 ms |
138072 KB |
Output is correct |
13 |
Correct |
16 ms |
138076 KB |
Output is correct |
14 |
Correct |
15 ms |
138016 KB |
Output is correct |
15 |
Correct |
16 ms |
138072 KB |
Output is correct |
16 |
Correct |
16 ms |
138076 KB |
Output is correct |
17 |
Correct |
16 ms |
138076 KB |
Output is correct |
18 |
Correct |
17 ms |
138076 KB |
Output is correct |
19 |
Correct |
16 ms |
138076 KB |
Output is correct |
20 |
Correct |
16 ms |
138072 KB |
Output is correct |
21 |
Correct |
16 ms |
137820 KB |
Output is correct |
22 |
Correct |
16 ms |
137820 KB |
Output is correct |
23 |
Correct |
16 ms |
138076 KB |
Output is correct |
24 |
Correct |
16 ms |
138076 KB |
Output is correct |
25 |
Correct |
19 ms |
138076 KB |
Output is correct |
26 |
Correct |
16 ms |
138076 KB |
Output is correct |
27 |
Correct |
16 ms |
138152 KB |
Output is correct |
28 |
Correct |
16 ms |
138076 KB |
Output is correct |
29 |
Correct |
15 ms |
138076 KB |
Output is correct |
30 |
Correct |
16 ms |
138076 KB |
Output is correct |
31 |
Correct |
16 ms |
137888 KB |
Output is correct |
32 |
Correct |
16 ms |
138068 KB |
Output is correct |
33 |
Correct |
16 ms |
138076 KB |
Output is correct |
34 |
Correct |
16 ms |
138072 KB |
Output is correct |
35 |
Correct |
16 ms |
138120 KB |
Output is correct |
36 |
Correct |
16 ms |
138072 KB |
Output is correct |
37 |
Correct |
16 ms |
138076 KB |
Output is correct |
38 |
Correct |
14 ms |
137820 KB |
Output is correct |
39 |
Correct |
14 ms |
137820 KB |
Output is correct |
40 |
Correct |
15 ms |
138076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
133724 KB |
Output is correct |
2 |
Correct |
13 ms |
135664 KB |
Output is correct |
3 |
Correct |
14 ms |
137820 KB |
Output is correct |
4 |
Correct |
14 ms |
137816 KB |
Output is correct |
5 |
Correct |
13 ms |
137820 KB |
Output is correct |
6 |
Correct |
15 ms |
137816 KB |
Output is correct |
7 |
Correct |
19 ms |
148060 KB |
Output is correct |
8 |
Correct |
25 ms |
158492 KB |
Output is correct |
9 |
Correct |
27 ms |
159068 KB |
Output is correct |
10 |
Correct |
29 ms |
159064 KB |
Output is correct |
11 |
Correct |
27 ms |
159068 KB |
Output is correct |
12 |
Correct |
18 ms |
147056 KB |
Output is correct |
13 |
Correct |
13 ms |
133724 KB |
Output is correct |
14 |
Correct |
13 ms |
133676 KB |
Output is correct |
15 |
Correct |
12 ms |
133724 KB |
Output is correct |
16 |
Correct |
16 ms |
138124 KB |
Output is correct |
17 |
Correct |
18 ms |
138076 KB |
Output is correct |
18 |
Correct |
15 ms |
138076 KB |
Output is correct |
19 |
Correct |
16 ms |
138072 KB |
Output is correct |
20 |
Correct |
16 ms |
138076 KB |
Output is correct |
21 |
Correct |
15 ms |
138016 KB |
Output is correct |
22 |
Correct |
16 ms |
138072 KB |
Output is correct |
23 |
Correct |
16 ms |
138076 KB |
Output is correct |
24 |
Correct |
16 ms |
138076 KB |
Output is correct |
25 |
Correct |
17 ms |
138076 KB |
Output is correct |
26 |
Correct |
16 ms |
138076 KB |
Output is correct |
27 |
Correct |
16 ms |
138072 KB |
Output is correct |
28 |
Correct |
16 ms |
137820 KB |
Output is correct |
29 |
Correct |
16 ms |
137820 KB |
Output is correct |
30 |
Correct |
16 ms |
138076 KB |
Output is correct |
31 |
Correct |
16 ms |
138076 KB |
Output is correct |
32 |
Correct |
19 ms |
138076 KB |
Output is correct |
33 |
Correct |
16 ms |
138076 KB |
Output is correct |
34 |
Correct |
16 ms |
138152 KB |
Output is correct |
35 |
Correct |
16 ms |
138076 KB |
Output is correct |
36 |
Correct |
15 ms |
138076 KB |
Output is correct |
37 |
Correct |
16 ms |
138076 KB |
Output is correct |
38 |
Correct |
16 ms |
137888 KB |
Output is correct |
39 |
Correct |
16 ms |
138068 KB |
Output is correct |
40 |
Correct |
16 ms |
138076 KB |
Output is correct |
41 |
Correct |
16 ms |
138072 KB |
Output is correct |
42 |
Correct |
16 ms |
138120 KB |
Output is correct |
43 |
Correct |
16 ms |
138072 KB |
Output is correct |
44 |
Correct |
16 ms |
138076 KB |
Output is correct |
45 |
Correct |
14 ms |
137820 KB |
Output is correct |
46 |
Correct |
14 ms |
137820 KB |
Output is correct |
47 |
Correct |
15 ms |
138076 KB |
Output is correct |
48 |
Correct |
648 ms |
175952 KB |
Output is correct |
49 |
Correct |
1436 ms |
176408 KB |
Output is correct |
50 |
Correct |
1376 ms |
176508 KB |
Output is correct |
51 |
Correct |
1327 ms |
176324 KB |
Output is correct |
52 |
Correct |
1391 ms |
176184 KB |
Output is correct |
53 |
Correct |
1439 ms |
176248 KB |
Output is correct |
54 |
Correct |
1350 ms |
176200 KB |
Output is correct |
55 |
Correct |
583 ms |
176116 KB |
Output is correct |
56 |
Correct |
1241 ms |
176308 KB |
Output is correct |
57 |
Correct |
1213 ms |
176436 KB |
Output is correct |
58 |
Correct |
1289 ms |
176188 KB |
Output is correct |
59 |
Correct |
1394 ms |
176188 KB |
Output is correct |
60 |
Correct |
1301 ms |
176192 KB |
Output is correct |
61 |
Correct |
1250 ms |
176212 KB |
Output is correct |
62 |
Correct |
70 ms |
159320 KB |
Output is correct |
63 |
Correct |
16 ms |
133980 KB |
Output is correct |
64 |
Correct |
1525 ms |
168104 KB |
Output is correct |
65 |
Correct |
1196 ms |
158464 KB |
Output is correct |
66 |
Correct |
2342 ms |
176400 KB |
Output is correct |
67 |
Correct |
2819 ms |
176188 KB |
Output is correct |
68 |
Correct |
2747 ms |
176188 KB |
Output is correct |
69 |
Correct |
1846 ms |
176144 KB |
Output is correct |
70 |
Correct |
2415 ms |
176296 KB |
Output is correct |
71 |
Correct |
2533 ms |
176184 KB |
Output is correct |
72 |
Correct |
2612 ms |
176248 KB |
Output is correct |
73 |
Correct |
2458 ms |
176420 KB |
Output is correct |
74 |
Correct |
2548 ms |
176216 KB |
Output is correct |
75 |
Correct |
84 ms |
147756 KB |
Output is correct |
76 |
Correct |
83 ms |
147540 KB |
Output is correct |
77 |
Correct |
81 ms |
147764 KB |
Output is correct |
78 |
Correct |
1105 ms |
176432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
133724 KB |
Output is correct |
2 |
Correct |
13 ms |
135664 KB |
Output is correct |
3 |
Correct |
14 ms |
137820 KB |
Output is correct |
4 |
Correct |
14 ms |
137816 KB |
Output is correct |
5 |
Correct |
13 ms |
137820 KB |
Output is correct |
6 |
Correct |
15 ms |
137816 KB |
Output is correct |
7 |
Correct |
19 ms |
148060 KB |
Output is correct |
8 |
Correct |
25 ms |
158492 KB |
Output is correct |
9 |
Correct |
27 ms |
159068 KB |
Output is correct |
10 |
Correct |
29 ms |
159064 KB |
Output is correct |
11 |
Correct |
27 ms |
159068 KB |
Output is correct |
12 |
Correct |
18 ms |
147056 KB |
Output is correct |
13 |
Correct |
13 ms |
133724 KB |
Output is correct |
14 |
Correct |
13 ms |
133676 KB |
Output is correct |
15 |
Correct |
12 ms |
133724 KB |
Output is correct |
16 |
Correct |
14 ms |
133724 KB |
Output is correct |
17 |
Correct |
13 ms |
133804 KB |
Output is correct |
18 |
Correct |
15 ms |
133724 KB |
Output is correct |
19 |
Correct |
15 ms |
133980 KB |
Output is correct |
20 |
Correct |
14 ms |
133792 KB |
Output is correct |
21 |
Correct |
14 ms |
133764 KB |
Output is correct |
22 |
Correct |
13 ms |
133724 KB |
Output is correct |
23 |
Correct |
15 ms |
133956 KB |
Output is correct |
24 |
Correct |
15 ms |
133980 KB |
Output is correct |
25 |
Correct |
14 ms |
133736 KB |
Output is correct |
26 |
Correct |
14 ms |
133724 KB |
Output is correct |
27 |
Correct |
16 ms |
138124 KB |
Output is correct |
28 |
Correct |
18 ms |
138076 KB |
Output is correct |
29 |
Correct |
15 ms |
138076 KB |
Output is correct |
30 |
Correct |
16 ms |
138072 KB |
Output is correct |
31 |
Correct |
16 ms |
138076 KB |
Output is correct |
32 |
Correct |
15 ms |
138016 KB |
Output is correct |
33 |
Correct |
16 ms |
138072 KB |
Output is correct |
34 |
Correct |
16 ms |
138076 KB |
Output is correct |
35 |
Correct |
16 ms |
138076 KB |
Output is correct |
36 |
Correct |
17 ms |
138076 KB |
Output is correct |
37 |
Correct |
16 ms |
138076 KB |
Output is correct |
38 |
Correct |
16 ms |
138072 KB |
Output is correct |
39 |
Correct |
16 ms |
137820 KB |
Output is correct |
40 |
Correct |
16 ms |
137820 KB |
Output is correct |
41 |
Correct |
16 ms |
138076 KB |
Output is correct |
42 |
Correct |
16 ms |
138076 KB |
Output is correct |
43 |
Correct |
19 ms |
138076 KB |
Output is correct |
44 |
Correct |
16 ms |
138076 KB |
Output is correct |
45 |
Correct |
16 ms |
138152 KB |
Output is correct |
46 |
Correct |
16 ms |
138076 KB |
Output is correct |
47 |
Correct |
15 ms |
138076 KB |
Output is correct |
48 |
Correct |
16 ms |
138076 KB |
Output is correct |
49 |
Correct |
16 ms |
137888 KB |
Output is correct |
50 |
Correct |
16 ms |
138068 KB |
Output is correct |
51 |
Correct |
16 ms |
138076 KB |
Output is correct |
52 |
Correct |
16 ms |
138072 KB |
Output is correct |
53 |
Correct |
16 ms |
138120 KB |
Output is correct |
54 |
Correct |
16 ms |
138072 KB |
Output is correct |
55 |
Correct |
16 ms |
138076 KB |
Output is correct |
56 |
Correct |
14 ms |
137820 KB |
Output is correct |
57 |
Correct |
14 ms |
137820 KB |
Output is correct |
58 |
Correct |
15 ms |
138076 KB |
Output is correct |
59 |
Correct |
648 ms |
175952 KB |
Output is correct |
60 |
Correct |
1436 ms |
176408 KB |
Output is correct |
61 |
Correct |
1376 ms |
176508 KB |
Output is correct |
62 |
Correct |
1327 ms |
176324 KB |
Output is correct |
63 |
Correct |
1391 ms |
176184 KB |
Output is correct |
64 |
Correct |
1439 ms |
176248 KB |
Output is correct |
65 |
Correct |
1350 ms |
176200 KB |
Output is correct |
66 |
Correct |
583 ms |
176116 KB |
Output is correct |
67 |
Correct |
1241 ms |
176308 KB |
Output is correct |
68 |
Correct |
1213 ms |
176436 KB |
Output is correct |
69 |
Correct |
1289 ms |
176188 KB |
Output is correct |
70 |
Correct |
1394 ms |
176188 KB |
Output is correct |
71 |
Correct |
1301 ms |
176192 KB |
Output is correct |
72 |
Correct |
1250 ms |
176212 KB |
Output is correct |
73 |
Correct |
70 ms |
159320 KB |
Output is correct |
74 |
Correct |
16 ms |
133980 KB |
Output is correct |
75 |
Correct |
1525 ms |
168104 KB |
Output is correct |
76 |
Correct |
1196 ms |
158464 KB |
Output is correct |
77 |
Correct |
2342 ms |
176400 KB |
Output is correct |
78 |
Correct |
2819 ms |
176188 KB |
Output is correct |
79 |
Correct |
2747 ms |
176188 KB |
Output is correct |
80 |
Correct |
1846 ms |
176144 KB |
Output is correct |
81 |
Correct |
2415 ms |
176296 KB |
Output is correct |
82 |
Correct |
2533 ms |
176184 KB |
Output is correct |
83 |
Correct |
2612 ms |
176248 KB |
Output is correct |
84 |
Correct |
2458 ms |
176420 KB |
Output is correct |
85 |
Correct |
2548 ms |
176216 KB |
Output is correct |
86 |
Correct |
84 ms |
147756 KB |
Output is correct |
87 |
Correct |
83 ms |
147540 KB |
Output is correct |
88 |
Correct |
81 ms |
147764 KB |
Output is correct |
89 |
Correct |
1105 ms |
176432 KB |
Output is correct |
90 |
Execution timed out |
3516 ms |
177496 KB |
Time limit exceeded |
91 |
Halted |
0 ms |
0 KB |
- |