#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=LLONG_MAX;
const int maxn=1e3+5;
#define pii pair<int,int>
#define fi first
#define se second
struct bus{
long long s,t;
int id;
bool operator<(bus o){
if(s!=o.s) return s<o.s;
else return t<o.t;
}
};
int M,N;
long long X,L;
vector<long long> T,S,W;
bus B[maxn][maxn];
long long res[maxn][maxn];
namespace Segtree{
int n;
vector<pii> tree;
vector<long long> com;
void add(long long x){
com.push_back(x);
}
void build(){
sort(com.begin(),com.end());
com.erase(unique(com.begin(),com.end()),com.end());
n=(int)com.size();
tree.assign(4*n,make_pair(M,0));
}
void update(int l,int r,int id,int tl,int tr,pii x){
if(tr<l || r<tl) return;
if(tl<=l && r<=tr) return tree[id]=min(tree[id],x),void();
int mid=(l+r)>>1;
update(l,mid,id<<1,tl,tr,x);update(mid+1,r,id<<1|1,tl,tr,x);
}
void update(long long l,long long r,pii x){
if(l>r) return;
int pl=upper_bound(com.begin(),com.end(),l)-com.begin();
int pr=upper_bound(com.begin(),com.end(),r)-com.begin();
update(1,n,1,pl,pr,x);
}
pii query(int l,int r,int id,int x){
if(l==r) return tree[id];
int mid=(l+r)>>1;
pii res=tree[id];
if(x<=mid) res=min(res,query(l,mid,id<<1,x));
else res=min(res,query(mid+1,r,id<<1|1,x));
return res;
}
pii query(long long x){
int px=upper_bound(com.begin(),com.end(),x)-com.begin();
return query(1,n,1,px);
}
}
void init(int l, int n, vector<long long> st, vector<int> w, int x, int m, vector<int> s)
{
L=l;N=n;X=x;M=m;T=st;
W.resize(N);S.resize(M);
for(int i=0;i<N;i++) W[i]=w[i];
for(int i=0;i<M;i++) S[i]=s[i];
for(int i=0;i<N;i++) B[0][i]={0,T[i],i};
for(int i=1;i<M;i++){
for(int j=0;j<N;j++){
auto [ss,tt,id]=B[i-1][j];
B[i][j]={tt,tt+(S[i]-S[i-1])*W[id],id};
}
sort(B[i],B[i]+N);
for(int j=1;j<N;j++) B[i][j].t=max(B[i][j].t,B[i][j-1].t);
for(int j=0;j<N;j++){
Segtree::add(B[i][j].s-X*S[i-1]+1);
Segtree::add(B[i][j].t-X*S[i]);
}
}
Segtree::add(-inf);
Segtree::build();
for(int i=M-1;i>=1;i--){
for(int j=0;j<N;j++){
pii pos=Segtree::query(B[i][j].t-X*S[i]);pos.se=-pos.se;
if(pos.fi==M) res[i][j]=B[i][j].t+X*(L-S[i]);
else res[i][j]=res[pos.fi][pos.se];
//cout << res[i][j] << ' ';
}
for(int j=0;j<N;j++) Segtree::update(B[i][j].s-X*S[i-1]+1,B[i][j].t-X*S[i]-1,{i,-j});
//cout << '\n';
}
}
long long arrival_time(long long cur)
{
pii pos=Segtree::query(cur);pos.se=-pos.se;
//cout << pos.fi << ' ' << pos.se << ' ' << B[pos.fi][pos.se].id << '\n';
if(pos.fi==M) return cur+X*L;
else return res[pos.fi][pos.se];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
6596 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
27228 KB |
Output is correct |
8 |
Correct |
4 ms |
31324 KB |
Output is correct |
9 |
Correct |
4 ms |
31320 KB |
Output is correct |
10 |
Correct |
4 ms |
31324 KB |
Output is correct |
11 |
Correct |
4 ms |
31320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2512 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
2 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2648 KB |
Output is correct |
11 |
Correct |
1 ms |
2392 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
6596 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2512 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
7 ms |
7548 KB |
Output is correct |
10 |
Correct |
7 ms |
7384 KB |
Output is correct |
11 |
Correct |
7 ms |
7512 KB |
Output is correct |
12 |
Correct |
7 ms |
7792 KB |
Output is correct |
13 |
Correct |
7 ms |
7404 KB |
Output is correct |
14 |
Correct |
7 ms |
7384 KB |
Output is correct |
15 |
Correct |
7 ms |
7384 KB |
Output is correct |
16 |
Correct |
6 ms |
7384 KB |
Output is correct |
17 |
Correct |
6 ms |
7384 KB |
Output is correct |
18 |
Correct |
7 ms |
7380 KB |
Output is correct |
19 |
Correct |
7 ms |
7384 KB |
Output is correct |
20 |
Correct |
7 ms |
7384 KB |
Output is correct |
21 |
Correct |
4 ms |
7004 KB |
Output is correct |
22 |
Correct |
4 ms |
7004 KB |
Output is correct |
23 |
Correct |
3 ms |
6748 KB |
Output is correct |
24 |
Correct |
7 ms |
7408 KB |
Output is correct |
25 |
Correct |
6 ms |
7512 KB |
Output is correct |
26 |
Correct |
6 ms |
7260 KB |
Output is correct |
27 |
Correct |
6 ms |
7260 KB |
Output is correct |
28 |
Correct |
4 ms |
7256 KB |
Output is correct |
29 |
Correct |
4 ms |
7260 KB |
Output is correct |
30 |
Correct |
5 ms |
7260 KB |
Output is correct |
31 |
Correct |
4 ms |
7260 KB |
Output is correct |
32 |
Correct |
4 ms |
7128 KB |
Output is correct |
33 |
Correct |
6 ms |
7384 KB |
Output is correct |
34 |
Correct |
6 ms |
7520 KB |
Output is correct |
35 |
Correct |
7 ms |
7384 KB |
Output is correct |
36 |
Correct |
6 ms |
7384 KB |
Output is correct |
37 |
Correct |
6 ms |
7384 KB |
Output is correct |
38 |
Correct |
2 ms |
6872 KB |
Output is correct |
39 |
Correct |
3 ms |
6872 KB |
Output is correct |
40 |
Correct |
5 ms |
7108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
6596 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
27228 KB |
Output is correct |
9 |
Correct |
4 ms |
31324 KB |
Output is correct |
10 |
Correct |
4 ms |
31320 KB |
Output is correct |
11 |
Correct |
4 ms |
31324 KB |
Output is correct |
12 |
Correct |
4 ms |
31320 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2512 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
7 ms |
7548 KB |
Output is correct |
17 |
Correct |
7 ms |
7384 KB |
Output is correct |
18 |
Correct |
7 ms |
7512 KB |
Output is correct |
19 |
Correct |
7 ms |
7792 KB |
Output is correct |
20 |
Correct |
7 ms |
7404 KB |
Output is correct |
21 |
Correct |
7 ms |
7384 KB |
Output is correct |
22 |
Correct |
7 ms |
7384 KB |
Output is correct |
23 |
Correct |
6 ms |
7384 KB |
Output is correct |
24 |
Correct |
6 ms |
7384 KB |
Output is correct |
25 |
Correct |
7 ms |
7380 KB |
Output is correct |
26 |
Correct |
7 ms |
7384 KB |
Output is correct |
27 |
Correct |
7 ms |
7384 KB |
Output is correct |
28 |
Correct |
4 ms |
7004 KB |
Output is correct |
29 |
Correct |
4 ms |
7004 KB |
Output is correct |
30 |
Correct |
3 ms |
6748 KB |
Output is correct |
31 |
Correct |
7 ms |
7408 KB |
Output is correct |
32 |
Correct |
6 ms |
7512 KB |
Output is correct |
33 |
Correct |
6 ms |
7260 KB |
Output is correct |
34 |
Correct |
6 ms |
7260 KB |
Output is correct |
35 |
Correct |
4 ms |
7256 KB |
Output is correct |
36 |
Correct |
4 ms |
7260 KB |
Output is correct |
37 |
Correct |
5 ms |
7260 KB |
Output is correct |
38 |
Correct |
4 ms |
7260 KB |
Output is correct |
39 |
Correct |
4 ms |
7128 KB |
Output is correct |
40 |
Correct |
6 ms |
7384 KB |
Output is correct |
41 |
Correct |
6 ms |
7520 KB |
Output is correct |
42 |
Correct |
7 ms |
7384 KB |
Output is correct |
43 |
Correct |
6 ms |
7384 KB |
Output is correct |
44 |
Correct |
6 ms |
7384 KB |
Output is correct |
45 |
Correct |
2 ms |
6872 KB |
Output is correct |
46 |
Correct |
3 ms |
6872 KB |
Output is correct |
47 |
Correct |
5 ms |
7108 KB |
Output is correct |
48 |
Correct |
1038 ms |
102280 KB |
Output is correct |
49 |
Correct |
978 ms |
107176 KB |
Output is correct |
50 |
Correct |
995 ms |
108716 KB |
Output is correct |
51 |
Correct |
980 ms |
107884 KB |
Output is correct |
52 |
Correct |
986 ms |
107432 KB |
Output is correct |
53 |
Correct |
967 ms |
107688 KB |
Output is correct |
54 |
Correct |
958 ms |
107976 KB |
Output is correct |
55 |
Correct |
800 ms |
85416 KB |
Output is correct |
56 |
Correct |
849 ms |
107240 KB |
Output is correct |
57 |
Correct |
823 ms |
103348 KB |
Output is correct |
58 |
Correct |
887 ms |
108204 KB |
Output is correct |
59 |
Correct |
888 ms |
106908 KB |
Output is correct |
60 |
Correct |
859 ms |
106920 KB |
Output is correct |
61 |
Correct |
875 ms |
107760 KB |
Output is correct |
62 |
Correct |
6 ms |
31540 KB |
Output is correct |
63 |
Correct |
2 ms |
2652 KB |
Output is correct |
64 |
Correct |
471 ms |
67924 KB |
Output is correct |
65 |
Correct |
470 ms |
55732 KB |
Output is correct |
66 |
Correct |
396 ms |
48296 KB |
Output is correct |
67 |
Correct |
1036 ms |
104136 KB |
Output is correct |
68 |
Correct |
1078 ms |
105472 KB |
Output is correct |
69 |
Correct |
415 ms |
79016 KB |
Output is correct |
70 |
Correct |
727 ms |
102572 KB |
Output is correct |
71 |
Correct |
796 ms |
110740 KB |
Output is correct |
72 |
Correct |
854 ms |
110156 KB |
Output is correct |
73 |
Correct |
802 ms |
110320 KB |
Output is correct |
74 |
Correct |
810 ms |
110336 KB |
Output is correct |
75 |
Correct |
216 ms |
47788 KB |
Output is correct |
76 |
Correct |
218 ms |
47976 KB |
Output is correct |
77 |
Correct |
222 ms |
47840 KB |
Output is correct |
78 |
Correct |
571 ms |
63292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
6596 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
27228 KB |
Output is correct |
9 |
Correct |
4 ms |
31324 KB |
Output is correct |
10 |
Correct |
4 ms |
31320 KB |
Output is correct |
11 |
Correct |
4 ms |
31324 KB |
Output is correct |
12 |
Correct |
4 ms |
31320 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2512 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
2 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
1 ms |
2648 KB |
Output is correct |
23 |
Correct |
1 ms |
2392 KB |
Output is correct |
24 |
Correct |
1 ms |
2396 KB |
Output is correct |
25 |
Correct |
1 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
7 ms |
7548 KB |
Output is correct |
28 |
Correct |
7 ms |
7384 KB |
Output is correct |
29 |
Correct |
7 ms |
7512 KB |
Output is correct |
30 |
Correct |
7 ms |
7792 KB |
Output is correct |
31 |
Correct |
7 ms |
7404 KB |
Output is correct |
32 |
Correct |
7 ms |
7384 KB |
Output is correct |
33 |
Correct |
7 ms |
7384 KB |
Output is correct |
34 |
Correct |
6 ms |
7384 KB |
Output is correct |
35 |
Correct |
6 ms |
7384 KB |
Output is correct |
36 |
Correct |
7 ms |
7380 KB |
Output is correct |
37 |
Correct |
7 ms |
7384 KB |
Output is correct |
38 |
Correct |
7 ms |
7384 KB |
Output is correct |
39 |
Correct |
4 ms |
7004 KB |
Output is correct |
40 |
Correct |
4 ms |
7004 KB |
Output is correct |
41 |
Correct |
3 ms |
6748 KB |
Output is correct |
42 |
Correct |
7 ms |
7408 KB |
Output is correct |
43 |
Correct |
6 ms |
7512 KB |
Output is correct |
44 |
Correct |
6 ms |
7260 KB |
Output is correct |
45 |
Correct |
6 ms |
7260 KB |
Output is correct |
46 |
Correct |
4 ms |
7256 KB |
Output is correct |
47 |
Correct |
4 ms |
7260 KB |
Output is correct |
48 |
Correct |
5 ms |
7260 KB |
Output is correct |
49 |
Correct |
4 ms |
7260 KB |
Output is correct |
50 |
Correct |
4 ms |
7128 KB |
Output is correct |
51 |
Correct |
6 ms |
7384 KB |
Output is correct |
52 |
Correct |
6 ms |
7520 KB |
Output is correct |
53 |
Correct |
7 ms |
7384 KB |
Output is correct |
54 |
Correct |
6 ms |
7384 KB |
Output is correct |
55 |
Correct |
6 ms |
7384 KB |
Output is correct |
56 |
Correct |
2 ms |
6872 KB |
Output is correct |
57 |
Correct |
3 ms |
6872 KB |
Output is correct |
58 |
Correct |
5 ms |
7108 KB |
Output is correct |
59 |
Correct |
1038 ms |
102280 KB |
Output is correct |
60 |
Correct |
978 ms |
107176 KB |
Output is correct |
61 |
Correct |
995 ms |
108716 KB |
Output is correct |
62 |
Correct |
980 ms |
107884 KB |
Output is correct |
63 |
Correct |
986 ms |
107432 KB |
Output is correct |
64 |
Correct |
967 ms |
107688 KB |
Output is correct |
65 |
Correct |
958 ms |
107976 KB |
Output is correct |
66 |
Correct |
800 ms |
85416 KB |
Output is correct |
67 |
Correct |
849 ms |
107240 KB |
Output is correct |
68 |
Correct |
823 ms |
103348 KB |
Output is correct |
69 |
Correct |
887 ms |
108204 KB |
Output is correct |
70 |
Correct |
888 ms |
106908 KB |
Output is correct |
71 |
Correct |
859 ms |
106920 KB |
Output is correct |
72 |
Correct |
875 ms |
107760 KB |
Output is correct |
73 |
Correct |
6 ms |
31540 KB |
Output is correct |
74 |
Correct |
2 ms |
2652 KB |
Output is correct |
75 |
Correct |
471 ms |
67924 KB |
Output is correct |
76 |
Correct |
470 ms |
55732 KB |
Output is correct |
77 |
Correct |
396 ms |
48296 KB |
Output is correct |
78 |
Correct |
1036 ms |
104136 KB |
Output is correct |
79 |
Correct |
1078 ms |
105472 KB |
Output is correct |
80 |
Correct |
415 ms |
79016 KB |
Output is correct |
81 |
Correct |
727 ms |
102572 KB |
Output is correct |
82 |
Correct |
796 ms |
110740 KB |
Output is correct |
83 |
Correct |
854 ms |
110156 KB |
Output is correct |
84 |
Correct |
802 ms |
110320 KB |
Output is correct |
85 |
Correct |
810 ms |
110336 KB |
Output is correct |
86 |
Correct |
216 ms |
47788 KB |
Output is correct |
87 |
Correct |
218 ms |
47976 KB |
Output is correct |
88 |
Correct |
222 ms |
47840 KB |
Output is correct |
89 |
Correct |
571 ms |
63292 KB |
Output is correct |
90 |
Correct |
1155 ms |
103804 KB |
Output is correct |
91 |
Correct |
1443 ms |
142228 KB |
Output is correct |
92 |
Correct |
1433 ms |
141940 KB |
Output is correct |
93 |
Correct |
1367 ms |
142008 KB |
Output is correct |
94 |
Correct |
1455 ms |
141552 KB |
Output is correct |
95 |
Correct |
1387 ms |
141636 KB |
Output is correct |
96 |
Correct |
1376 ms |
141848 KB |
Output is correct |
97 |
Correct |
841 ms |
88224 KB |
Output is correct |
98 |
Correct |
1284 ms |
141240 KB |
Output is correct |
99 |
Correct |
1279 ms |
138460 KB |
Output is correct |
100 |
Correct |
1313 ms |
141980 KB |
Output is correct |
101 |
Correct |
1339 ms |
140380 KB |
Output is correct |
102 |
Correct |
1322 ms |
140784 KB |
Output is correct |
103 |
Correct |
1335 ms |
142060 KB |
Output is correct |
104 |
Correct |
975 ms |
100620 KB |
Output is correct |
105 |
Correct |
988 ms |
91564 KB |
Output is correct |
106 |
Correct |
748 ms |
89848 KB |
Output is correct |
107 |
Correct |
1575 ms |
142016 KB |
Output is correct |
108 |
Correct |
1643 ms |
146224 KB |
Output is correct |
109 |
Correct |
1578 ms |
145196 KB |
Output is correct |
110 |
Correct |
1604 ms |
146540 KB |
Output is correct |
111 |
Correct |
803 ms |
114144 KB |
Output is correct |
112 |
Correct |
1188 ms |
137900 KB |
Output is correct |
113 |
Correct |
1353 ms |
146144 KB |
Output is correct |
114 |
Correct |
1535 ms |
147264 KB |
Output is correct |
115 |
Correct |
1299 ms |
145268 KB |
Output is correct |
116 |
Correct |
1233 ms |
145660 KB |
Output is correct |
117 |
Correct |
527 ms |
85932 KB |
Output is correct |
118 |
Correct |
538 ms |
86064 KB |
Output is correct |
119 |
Correct |
537 ms |
84084 KB |
Output is correct |
120 |
Correct |
548 ms |
86672 KB |
Output is correct |
121 |
Correct |
530 ms |
87340 KB |
Output is correct |
122 |
Correct |
947 ms |
92328 KB |
Output is correct |
123 |
Correct |
1544 ms |
146864 KB |
Output is correct |
124 |
Correct |
1608 ms |
147216 KB |
Output is correct |
125 |
Correct |
1620 ms |
147368 KB |
Output is correct |