#include <bits/stdc++.h>
#include "overtaking.h"
#define sz(x) (int)(size(x))
using namespace std;
using ll = long long;
constexpr ll inf = 2e18;
struct Segment{
ll l, r, y1, y2;
Segment(ll l_=0, ll r_=0, ll y1_=0, ll y2_=0):l(l_),r(r_),y1(y1_),y2(y2_){}
ll eval(ll x)const{
return y1 + (x-l)*((y2-y1)/(r-l));
}
Segment cut(ll cl, ll cr)const{
ll nl = max(l, cl);
ll nr = min(r, cr);
ll ny1 = eval(nl);
ll ny2 = eval(nr);
return {nl, nr, ny1, ny2};
};
bool operator<(const Segment& o)const{
if(l < o.l) return true;
if(l > o.l) return false;
return r < o.r;
}
};
using Fun = vector<Segment>;
Fun merge(const Fun& f, const Fun& g){ // g(f(x))
Fun res;
int i = 0;
for(Segment s : f){
while(i < sz(g) && g[i].r <= s.y1) i++;
if(s.y1 == s.y2){
ll y = g[i].eval(s.y1);
res.emplace_back(s.l, s.r, y, y);
}
else{
while(i < sz(g)){
Segment seg = g[i].cut(s.y1, s.y2);
ll offset = s.l - s.y1;
seg.l += offset, seg.r += offset;
res.push_back(seg);
if(seg.r < s.r) i++;
else break;
}
}
}
return res;
}
vector<Fun> funs;
Fun myFun;
Fun dcMerge(int l, int r){
if(l+1 == r) return funs[l];
int m = (l+r)/2;
Fun f = dcMerge(l, m);
Fun g = dcMerge(m, r);
return merge(f, g);
}
ll funEval(const Fun& f, ll x){
auto it = --lower_bound(f.begin(), f.end(), Segment{x+1, x+1, 0, 0});
return it->eval(x);
}
void dbg(const Fun& f){
for(Segment s : f){
cerr << s.l << " " << s.r << " " << s.y1 << " " << s.y2 << "\n";
}
cerr << "\n";
}
int L, M;
ll X;
vector<vector<pair<ll, ll>>> v;
vector<int> S;
void init(int Lin, int N, vector<ll> T, vector<int> W, int Xin, int Min, vector<int> Sin){
L = Lin, M = Min, X = Xin, S = Sin;
vector<int> ord(N);
for(int i = 0; i < N; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j){return T[i] < T[j];});
v.resize(M);
for(int i : ord){
if(W[i] <= X) continue;
if(v[0].empty()) v[0].emplace_back(T[i], (ll)W[i]);
else v[0].emplace_back(T[i], (ll)W[i]);
}
sort(v[0].begin(), v[0].end());
for(int k = 1; k < M; k++){
ll d = S[k]-S[k-1];
ll lt1 = -1, lt2 = 0;
Fun f;
auto addSeg = [&](ll t){
if(lt1 < t){
ll spl = min(t+1, max(lt1+1, lt2 - X*d));
if(spl > lt1+1) f.emplace_back(lt1+1, spl, lt2, lt2);
if(spl <= t) f.emplace_back(spl, t+1, spl + X*d, t+1 + X*d);
}
};
for(auto [t, w] : v[k-1]){
ll e = t+w*d;
ll t2 = max(lt2, e);
v[k].emplace_back(t2, w);
addSeg(t);
lt1 = t, lt2 = t2;
}
sort(v[k].begin(), v[k].end());
addSeg(inf);
funs.push_back(f);
// dbg(f);
}
myFun = dcMerge(0, M-1);
// dbg(myFun);
}
ll arrival_time(ll Y){
return funEval(myFun, Y);
// ll t = Y;
// for(int k = 0; k < M-1; k++){
// t = funEval(funs[k], t);
// }
// return t;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 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 |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 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 |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
556 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 |
348 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
2624 KB |
Output is correct |
10 |
Correct |
3 ms |
2516 KB |
Output is correct |
11 |
Correct |
3 ms |
2748 KB |
Output is correct |
12 |
Correct |
3 ms |
2984 KB |
Output is correct |
13 |
Correct |
3 ms |
2496 KB |
Output is correct |
14 |
Correct |
3 ms |
2732 KB |
Output is correct |
15 |
Correct |
2 ms |
1580 KB |
Output is correct |
16 |
Correct |
2 ms |
1576 KB |
Output is correct |
17 |
Correct |
2 ms |
1628 KB |
Output is correct |
18 |
Correct |
2 ms |
1624 KB |
Output is correct |
19 |
Correct |
2 ms |
1616 KB |
Output is correct |
20 |
Correct |
2 ms |
1628 KB |
Output is correct |
21 |
Correct |
1 ms |
860 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
1 ms |
1116 KB |
Output is correct |
24 |
Correct |
1 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
1112 KB |
Output is correct |
26 |
Correct |
1 ms |
1116 KB |
Output is correct |
27 |
Correct |
1 ms |
1116 KB |
Output is correct |
28 |
Correct |
1 ms |
1116 KB |
Output is correct |
29 |
Correct |
1 ms |
860 KB |
Output is correct |
30 |
Correct |
1 ms |
1116 KB |
Output is correct |
31 |
Correct |
1 ms |
860 KB |
Output is correct |
32 |
Correct |
2 ms |
2000 KB |
Output is correct |
33 |
Correct |
5 ms |
2880 KB |
Output is correct |
34 |
Correct |
3 ms |
2968 KB |
Output is correct |
35 |
Correct |
4 ms |
2972 KB |
Output is correct |
36 |
Correct |
4 ms |
2972 KB |
Output is correct |
37 |
Correct |
3 ms |
2968 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
3 ms |
2184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
600 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 |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
2624 KB |
Output is correct |
17 |
Correct |
3 ms |
2516 KB |
Output is correct |
18 |
Correct |
3 ms |
2748 KB |
Output is correct |
19 |
Correct |
3 ms |
2984 KB |
Output is correct |
20 |
Correct |
3 ms |
2496 KB |
Output is correct |
21 |
Correct |
3 ms |
2732 KB |
Output is correct |
22 |
Correct |
2 ms |
1580 KB |
Output is correct |
23 |
Correct |
2 ms |
1576 KB |
Output is correct |
24 |
Correct |
2 ms |
1628 KB |
Output is correct |
25 |
Correct |
2 ms |
1624 KB |
Output is correct |
26 |
Correct |
2 ms |
1616 KB |
Output is correct |
27 |
Correct |
2 ms |
1628 KB |
Output is correct |
28 |
Correct |
1 ms |
860 KB |
Output is correct |
29 |
Correct |
1 ms |
860 KB |
Output is correct |
30 |
Correct |
1 ms |
1116 KB |
Output is correct |
31 |
Correct |
1 ms |
1116 KB |
Output is correct |
32 |
Correct |
2 ms |
1112 KB |
Output is correct |
33 |
Correct |
1 ms |
1116 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
35 |
Correct |
1 ms |
1116 KB |
Output is correct |
36 |
Correct |
1 ms |
860 KB |
Output is correct |
37 |
Correct |
1 ms |
1116 KB |
Output is correct |
38 |
Correct |
1 ms |
860 KB |
Output is correct |
39 |
Correct |
2 ms |
2000 KB |
Output is correct |
40 |
Correct |
5 ms |
2880 KB |
Output is correct |
41 |
Correct |
3 ms |
2968 KB |
Output is correct |
42 |
Correct |
4 ms |
2972 KB |
Output is correct |
43 |
Correct |
4 ms |
2972 KB |
Output is correct |
44 |
Correct |
3 ms |
2968 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
3 ms |
2184 KB |
Output is correct |
48 |
Correct |
125 ms |
83220 KB |
Output is correct |
49 |
Correct |
144 ms |
89164 KB |
Output is correct |
50 |
Correct |
162 ms |
100568 KB |
Output is correct |
51 |
Correct |
138 ms |
95004 KB |
Output is correct |
52 |
Correct |
146 ms |
94168 KB |
Output is correct |
53 |
Correct |
150 ms |
89288 KB |
Output is correct |
54 |
Correct |
137 ms |
95048 KB |
Output is correct |
55 |
Correct |
60 ms |
50564 KB |
Output is correct |
56 |
Correct |
106 ms |
82296 KB |
Output is correct |
57 |
Correct |
109 ms |
83796 KB |
Output is correct |
58 |
Correct |
109 ms |
76768 KB |
Output is correct |
59 |
Correct |
112 ms |
89544 KB |
Output is correct |
60 |
Correct |
106 ms |
82184 KB |
Output is correct |
61 |
Correct |
106 ms |
76796 KB |
Output is correct |
62 |
Correct |
4 ms |
860 KB |
Output is correct |
63 |
Correct |
2 ms |
604 KB |
Output is correct |
64 |
Correct |
60 ms |
35896 KB |
Output is correct |
65 |
Correct |
47 ms |
35556 KB |
Output is correct |
66 |
Correct |
87 ms |
75956 KB |
Output is correct |
67 |
Correct |
103 ms |
72612 KB |
Output is correct |
68 |
Correct |
99 ms |
72292 KB |
Output is correct |
69 |
Correct |
188 ms |
128456 KB |
Output is correct |
70 |
Correct |
291 ms |
233000 KB |
Output is correct |
71 |
Correct |
307 ms |
216568 KB |
Output is correct |
72 |
Correct |
308 ms |
214480 KB |
Output is correct |
73 |
Correct |
310 ms |
217516 KB |
Output is correct |
74 |
Correct |
304 ms |
218984 KB |
Output is correct |
75 |
Correct |
2 ms |
600 KB |
Output is correct |
76 |
Correct |
2 ms |
604 KB |
Output is correct |
77 |
Correct |
2 ms |
604 KB |
Output is correct |
78 |
Correct |
234 ms |
158456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
600 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 |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
556 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
4 ms |
2624 KB |
Output is correct |
28 |
Correct |
3 ms |
2516 KB |
Output is correct |
29 |
Correct |
3 ms |
2748 KB |
Output is correct |
30 |
Correct |
3 ms |
2984 KB |
Output is correct |
31 |
Correct |
3 ms |
2496 KB |
Output is correct |
32 |
Correct |
3 ms |
2732 KB |
Output is correct |
33 |
Correct |
2 ms |
1580 KB |
Output is correct |
34 |
Correct |
2 ms |
1576 KB |
Output is correct |
35 |
Correct |
2 ms |
1628 KB |
Output is correct |
36 |
Correct |
2 ms |
1624 KB |
Output is correct |
37 |
Correct |
2 ms |
1616 KB |
Output is correct |
38 |
Correct |
2 ms |
1628 KB |
Output is correct |
39 |
Correct |
1 ms |
860 KB |
Output is correct |
40 |
Correct |
1 ms |
860 KB |
Output is correct |
41 |
Correct |
1 ms |
1116 KB |
Output is correct |
42 |
Correct |
1 ms |
1116 KB |
Output is correct |
43 |
Correct |
2 ms |
1112 KB |
Output is correct |
44 |
Correct |
1 ms |
1116 KB |
Output is correct |
45 |
Correct |
1 ms |
1116 KB |
Output is correct |
46 |
Correct |
1 ms |
1116 KB |
Output is correct |
47 |
Correct |
1 ms |
860 KB |
Output is correct |
48 |
Correct |
1 ms |
1116 KB |
Output is correct |
49 |
Correct |
1 ms |
860 KB |
Output is correct |
50 |
Correct |
2 ms |
2000 KB |
Output is correct |
51 |
Correct |
5 ms |
2880 KB |
Output is correct |
52 |
Correct |
3 ms |
2968 KB |
Output is correct |
53 |
Correct |
4 ms |
2972 KB |
Output is correct |
54 |
Correct |
4 ms |
2972 KB |
Output is correct |
55 |
Correct |
3 ms |
2968 KB |
Output is correct |
56 |
Correct |
0 ms |
348 KB |
Output is correct |
57 |
Correct |
0 ms |
348 KB |
Output is correct |
58 |
Correct |
3 ms |
2184 KB |
Output is correct |
59 |
Correct |
125 ms |
83220 KB |
Output is correct |
60 |
Correct |
144 ms |
89164 KB |
Output is correct |
61 |
Correct |
162 ms |
100568 KB |
Output is correct |
62 |
Correct |
138 ms |
95004 KB |
Output is correct |
63 |
Correct |
146 ms |
94168 KB |
Output is correct |
64 |
Correct |
150 ms |
89288 KB |
Output is correct |
65 |
Correct |
137 ms |
95048 KB |
Output is correct |
66 |
Correct |
60 ms |
50564 KB |
Output is correct |
67 |
Correct |
106 ms |
82296 KB |
Output is correct |
68 |
Correct |
109 ms |
83796 KB |
Output is correct |
69 |
Correct |
109 ms |
76768 KB |
Output is correct |
70 |
Correct |
112 ms |
89544 KB |
Output is correct |
71 |
Correct |
106 ms |
82184 KB |
Output is correct |
72 |
Correct |
106 ms |
76796 KB |
Output is correct |
73 |
Correct |
4 ms |
860 KB |
Output is correct |
74 |
Correct |
2 ms |
604 KB |
Output is correct |
75 |
Correct |
60 ms |
35896 KB |
Output is correct |
76 |
Correct |
47 ms |
35556 KB |
Output is correct |
77 |
Correct |
87 ms |
75956 KB |
Output is correct |
78 |
Correct |
103 ms |
72612 KB |
Output is correct |
79 |
Correct |
99 ms |
72292 KB |
Output is correct |
80 |
Correct |
188 ms |
128456 KB |
Output is correct |
81 |
Correct |
291 ms |
233000 KB |
Output is correct |
82 |
Correct |
307 ms |
216568 KB |
Output is correct |
83 |
Correct |
308 ms |
214480 KB |
Output is correct |
84 |
Correct |
310 ms |
217516 KB |
Output is correct |
85 |
Correct |
304 ms |
218984 KB |
Output is correct |
86 |
Correct |
2 ms |
600 KB |
Output is correct |
87 |
Correct |
2 ms |
604 KB |
Output is correct |
88 |
Correct |
2 ms |
604 KB |
Output is correct |
89 |
Correct |
234 ms |
158456 KB |
Output is correct |
90 |
Correct |
149 ms |
82648 KB |
Output is correct |
91 |
Correct |
391 ms |
113948 KB |
Output is correct |
92 |
Correct |
410 ms |
112468 KB |
Output is correct |
93 |
Correct |
356 ms |
108208 KB |
Output is correct |
94 |
Correct |
364 ms |
116220 KB |
Output is correct |
95 |
Correct |
364 ms |
113668 KB |
Output is correct |
96 |
Correct |
361 ms |
108152 KB |
Output is correct |
97 |
Correct |
84 ms |
52404 KB |
Output is correct |
98 |
Correct |
332 ms |
100340 KB |
Output is correct |
99 |
Correct |
335 ms |
98156 KB |
Output is correct |
100 |
Correct |
335 ms |
110988 KB |
Output is correct |
101 |
Correct |
340 ms |
106544 KB |
Output is correct |
102 |
Correct |
333 ms |
100196 KB |
Output is correct |
103 |
Correct |
338 ms |
111076 KB |
Output is correct |
104 |
Correct |
266 ms |
57656 KB |
Output is correct |
105 |
Correct |
284 ms |
58584 KB |
Output is correct |
106 |
Correct |
339 ms |
104364 KB |
Output is correct |
107 |
Correct |
339 ms |
95640 KB |
Output is correct |
108 |
Correct |
339 ms |
98220 KB |
Output is correct |
109 |
Correct |
336 ms |
95248 KB |
Output is correct |
110 |
Correct |
346 ms |
98560 KB |
Output is correct |
111 |
Correct |
492 ms |
138284 KB |
Output is correct |
112 |
Correct |
626 ms |
204500 KB |
Output is correct |
113 |
Correct |
750 ms |
226864 KB |
Output is correct |
114 |
Correct |
736 ms |
213956 KB |
Output is correct |
115 |
Correct |
694 ms |
226380 KB |
Output is correct |
116 |
Correct |
640 ms |
226560 KB |
Output is correct |
117 |
Correct |
178 ms |
28236 KB |
Output is correct |
118 |
Correct |
180 ms |
28296 KB |
Output is correct |
119 |
Correct |
178 ms |
27024 KB |
Output is correct |
120 |
Correct |
191 ms |
28444 KB |
Output is correct |
121 |
Correct |
176 ms |
29256 KB |
Output is correct |
122 |
Correct |
487 ms |
166516 KB |
Output is correct |
123 |
Correct |
721 ms |
217024 KB |
Output is correct |
124 |
Correct |
707 ms |
204660 KB |
Output is correct |
125 |
Correct |
689 ms |
202612 KB |
Output is correct |