#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long speed;
const long long inf=1e18+10;
vector<vector<long long>> ta;
vector<vector<pair<long long, long long>>> pr;
long long asdf=0;
namespace ST {
static const long long NN=1e6;
static const int LG=30;
int ndcnt=1;
long long RR=inf;
long long T[NN*LG], T2[NN*LG];
long long L[NN*LG], R[NN*LG];
void update1(long long ll, long long rr, long long val, long long l=0, long long r=0, long long v=1) {
if(r<ll or rr<l)return;
if(ll<=l and r<=rr) {
T[v]=max(T[v], val);
T2[v]=max(T2[v], T[v]);
return;
}
long long mid=(l+r)/2;
if(L[v]==0)L[v]=++ndcnt;
if(R[v]==0)R[v]=++ndcnt;
update1(ll, rr, val, l, mid, L[v]);
update1(ll, rr, val, mid+1, r, R[v]);
T2[v]=max(T2[v], max(T2[L[v]], T2[R[v]]));
}
long long query1(long long x, long long l, long long r, long long v) {
if(v==0)return 0;
long long mid=(l+r)/2;
if(x <= mid) {
return max(T[v], query1(x, l, mid, L[v]));
}
else return max(T[v], query1(x, mid+1, r, R[v]));
}
void update(long long l, long long r, long long val) {
update1(l, r, val, 0, RR, 1);
}
long long query(long long x) {
return max(x, query1(x, 0, RR, 1));
}
long long get(long long x, long long tmpval = 0, long long l=0, long long r=RR, long long v=1){
if(v==0) {
if(tmpval>x)return l;
if(r>x)return x+1;
return -1;
}
tmpval=max(tmpval, T[v]);
long long mid=(l+r)/2;
if(max(mid, max(tmpval, T2[L[v]]))>x)return get(x, tmpval, l, mid, L[v]);
long long ttt=get(x, tmpval, mid+1, r, R[v]);
if(ttt!=-1) {
return ttt;
}
if(max(r, tmpval) > x) {
if(tmpval>x)return l;
return x+1;
}
return -1;
}
};
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
speed=X;
asdf=S.back()*speed;
ta=vector<vector<long long>> (M, vector<long long> (N));
for(int i = 0;i<M;i++) {
for(int j = 0;j<N;j++) {
if(i==0)ta[i][j]=T[j];
else ta[i][j]=ta[i-1][j]+(long long)(S[i]-S[i-1])*W[j];
}
if(i){
vector<pair<pair<long long, long long>, int>> idxx;
for(int j = 0;j<N;j++) {
idxx.push_back({{ta[i-1][j], ta[i][j]}, j});
}
sort(idxx.begin(), idxx.end());
for(int k = 1;k<N;k++) {
ta[i][idxx[k].second]=max(ta[i][idxx[k].second], ta[i][idxx[k-1].second]);
}
}
}
pr.resize(M);
for(int i = 0 ;i<M;i++) {
vector<long long> idx;
for(int j = 0;j<N;j++) {
ta[i][j]-=S[i]*speed;
}
if(i) {
for(int j = 0;j<N;j++) {
long long lo = 0, hi = inf;
long long LL=ST::get(ta[i-1][j]);
idx.push_back(LL);
}
for(int j = 0;j<N;j++) {
if(idx[j]==-1)continue;
ST::update(idx[j], (long long)inf, ta[i][j]);
}
}
}
}
long long arrival_time(long long Y) {
long long ans=ST::query(Y);
return ans+asdf;
}
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:95:21: warning: unused variable 'lo' [-Wunused-variable]
95 | long long lo = 0, hi = inf;
| ^~
overtaking.cpp:95:29: warning: unused variable 'hi' [-Wunused-variable]
95 | long long lo = 0, hi = inf;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
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 |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 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 |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1372 KB |
Output is correct |
8 |
Correct |
2 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
2396 KB |
Output is correct |
10 |
Correct |
2 ms |
1628 KB |
Output is correct |
11 |
Correct |
2 ms |
1372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
856 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
2 ms |
1372 KB |
Output is correct |
7 |
Correct |
2 ms |
1628 KB |
Output is correct |
8 |
Correct |
2 ms |
1628 KB |
Output is correct |
9 |
Correct |
2 ms |
1628 KB |
Output is correct |
10 |
Correct |
2 ms |
600 KB |
Output is correct |
11 |
Correct |
2 ms |
856 KB |
Output is correct |
12 |
Correct |
2 ms |
1628 KB |
Output is correct |
13 |
Correct |
2 ms |
1116 KB |
Output is correct |
14 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 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 |
856 KB |
Output is correct |
9 |
Correct |
11 ms |
3932 KB |
Output is correct |
10 |
Correct |
12 ms |
5468 KB |
Output is correct |
11 |
Correct |
17 ms |
6492 KB |
Output is correct |
12 |
Correct |
12 ms |
5048 KB |
Output is correct |
13 |
Correct |
12 ms |
5212 KB |
Output is correct |
14 |
Correct |
13 ms |
4956 KB |
Output is correct |
15 |
Correct |
10 ms |
1628 KB |
Output is correct |
16 |
Correct |
11 ms |
1628 KB |
Output is correct |
17 |
Correct |
10 ms |
1628 KB |
Output is correct |
18 |
Correct |
10 ms |
1628 KB |
Output is correct |
19 |
Correct |
10 ms |
1628 KB |
Output is correct |
20 |
Correct |
10 ms |
1856 KB |
Output is correct |
21 |
Correct |
5 ms |
600 KB |
Output is correct |
22 |
Correct |
5 ms |
788 KB |
Output is correct |
23 |
Correct |
11 ms |
748 KB |
Output is correct |
24 |
Correct |
9 ms |
860 KB |
Output is correct |
25 |
Correct |
12 ms |
860 KB |
Output is correct |
26 |
Correct |
10 ms |
860 KB |
Output is correct |
27 |
Correct |
10 ms |
860 KB |
Output is correct |
28 |
Correct |
8 ms |
1112 KB |
Output is correct |
29 |
Correct |
7 ms |
604 KB |
Output is correct |
30 |
Correct |
8 ms |
860 KB |
Output is correct |
31 |
Correct |
7 ms |
860 KB |
Output is correct |
32 |
Correct |
10 ms |
1080 KB |
Output is correct |
33 |
Correct |
10 ms |
1580 KB |
Output is correct |
34 |
Correct |
13 ms |
4184 KB |
Output is correct |
35 |
Correct |
13 ms |
6744 KB |
Output is correct |
36 |
Correct |
11 ms |
4188 KB |
Output is correct |
37 |
Correct |
12 ms |
3932 KB |
Output is correct |
38 |
Correct |
6 ms |
604 KB |
Output is correct |
39 |
Correct |
7 ms |
600 KB |
Output is correct |
40 |
Correct |
9 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
2 ms |
1372 KB |
Output is correct |
9 |
Correct |
2 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
1628 KB |
Output is correct |
12 |
Correct |
2 ms |
1372 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
11 ms |
3932 KB |
Output is correct |
17 |
Correct |
12 ms |
5468 KB |
Output is correct |
18 |
Correct |
17 ms |
6492 KB |
Output is correct |
19 |
Correct |
12 ms |
5048 KB |
Output is correct |
20 |
Correct |
12 ms |
5212 KB |
Output is correct |
21 |
Correct |
13 ms |
4956 KB |
Output is correct |
22 |
Correct |
10 ms |
1628 KB |
Output is correct |
23 |
Correct |
11 ms |
1628 KB |
Output is correct |
24 |
Correct |
10 ms |
1628 KB |
Output is correct |
25 |
Correct |
10 ms |
1628 KB |
Output is correct |
26 |
Correct |
10 ms |
1628 KB |
Output is correct |
27 |
Correct |
10 ms |
1856 KB |
Output is correct |
28 |
Correct |
5 ms |
600 KB |
Output is correct |
29 |
Correct |
5 ms |
788 KB |
Output is correct |
30 |
Correct |
11 ms |
748 KB |
Output is correct |
31 |
Correct |
9 ms |
860 KB |
Output is correct |
32 |
Correct |
12 ms |
860 KB |
Output is correct |
33 |
Correct |
10 ms |
860 KB |
Output is correct |
34 |
Correct |
10 ms |
860 KB |
Output is correct |
35 |
Correct |
8 ms |
1112 KB |
Output is correct |
36 |
Correct |
7 ms |
604 KB |
Output is correct |
37 |
Correct |
8 ms |
860 KB |
Output is correct |
38 |
Correct |
7 ms |
860 KB |
Output is correct |
39 |
Correct |
10 ms |
1080 KB |
Output is correct |
40 |
Correct |
10 ms |
1580 KB |
Output is correct |
41 |
Correct |
13 ms |
4184 KB |
Output is correct |
42 |
Correct |
13 ms |
6744 KB |
Output is correct |
43 |
Correct |
11 ms |
4188 KB |
Output is correct |
44 |
Correct |
12 ms |
3932 KB |
Output is correct |
45 |
Correct |
6 ms |
604 KB |
Output is correct |
46 |
Correct |
7 ms |
600 KB |
Output is correct |
47 |
Correct |
9 ms |
856 KB |
Output is correct |
48 |
Correct |
1054 ms |
13896 KB |
Output is correct |
49 |
Correct |
1265 ms |
23592 KB |
Output is correct |
50 |
Correct |
1345 ms |
29628 KB |
Output is correct |
51 |
Correct |
1280 ms |
22808 KB |
Output is correct |
52 |
Correct |
1245 ms |
23728 KB |
Output is correct |
53 |
Correct |
1244 ms |
23396 KB |
Output is correct |
54 |
Correct |
1252 ms |
23120 KB |
Output is correct |
55 |
Correct |
871 ms |
10072 KB |
Output is correct |
56 |
Correct |
1086 ms |
18332 KB |
Output is correct |
57 |
Correct |
1204 ms |
19568 KB |
Output is correct |
58 |
Correct |
1112 ms |
18808 KB |
Output is correct |
59 |
Correct |
1105 ms |
18464 KB |
Output is correct |
60 |
Correct |
1082 ms |
18404 KB |
Output is correct |
61 |
Correct |
1136 ms |
18728 KB |
Output is correct |
62 |
Correct |
4 ms |
2396 KB |
Output is correct |
63 |
Correct |
4 ms |
1628 KB |
Output is correct |
64 |
Correct |
480 ms |
6256 KB |
Output is correct |
65 |
Correct |
621 ms |
6784 KB |
Output is correct |
66 |
Correct |
1536 ms |
12264 KB |
Output is correct |
67 |
Correct |
1382 ms |
13420 KB |
Output is correct |
68 |
Correct |
1412 ms |
13548 KB |
Output is correct |
69 |
Correct |
1421 ms |
72020 KB |
Output is correct |
70 |
Correct |
1502 ms |
110124 KB |
Output is correct |
71 |
Correct |
1771 ms |
333488 KB |
Output is correct |
72 |
Correct |
2023 ms |
515188 KB |
Output is correct |
73 |
Correct |
1643 ms |
380240 KB |
Output is correct |
74 |
Correct |
1733 ms |
379488 KB |
Output is correct |
75 |
Correct |
873 ms |
10680 KB |
Output is correct |
76 |
Correct |
871 ms |
10832 KB |
Output is correct |
77 |
Correct |
956 ms |
11248 KB |
Output is correct |
78 |
Correct |
1078 ms |
40020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
2 ms |
1372 KB |
Output is correct |
9 |
Correct |
2 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
1628 KB |
Output is correct |
12 |
Correct |
2 ms |
1372 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
860 KB |
Output is correct |
18 |
Correct |
2 ms |
1372 KB |
Output is correct |
19 |
Correct |
2 ms |
1628 KB |
Output is correct |
20 |
Correct |
2 ms |
1628 KB |
Output is correct |
21 |
Correct |
2 ms |
1628 KB |
Output is correct |
22 |
Correct |
2 ms |
600 KB |
Output is correct |
23 |
Correct |
2 ms |
856 KB |
Output is correct |
24 |
Correct |
2 ms |
1628 KB |
Output is correct |
25 |
Correct |
2 ms |
1116 KB |
Output is correct |
26 |
Correct |
2 ms |
1116 KB |
Output is correct |
27 |
Correct |
11 ms |
3932 KB |
Output is correct |
28 |
Correct |
12 ms |
5468 KB |
Output is correct |
29 |
Correct |
17 ms |
6492 KB |
Output is correct |
30 |
Correct |
12 ms |
5048 KB |
Output is correct |
31 |
Correct |
12 ms |
5212 KB |
Output is correct |
32 |
Correct |
13 ms |
4956 KB |
Output is correct |
33 |
Correct |
10 ms |
1628 KB |
Output is correct |
34 |
Correct |
11 ms |
1628 KB |
Output is correct |
35 |
Correct |
10 ms |
1628 KB |
Output is correct |
36 |
Correct |
10 ms |
1628 KB |
Output is correct |
37 |
Correct |
10 ms |
1628 KB |
Output is correct |
38 |
Correct |
10 ms |
1856 KB |
Output is correct |
39 |
Correct |
5 ms |
600 KB |
Output is correct |
40 |
Correct |
5 ms |
788 KB |
Output is correct |
41 |
Correct |
11 ms |
748 KB |
Output is correct |
42 |
Correct |
9 ms |
860 KB |
Output is correct |
43 |
Correct |
12 ms |
860 KB |
Output is correct |
44 |
Correct |
10 ms |
860 KB |
Output is correct |
45 |
Correct |
10 ms |
860 KB |
Output is correct |
46 |
Correct |
8 ms |
1112 KB |
Output is correct |
47 |
Correct |
7 ms |
604 KB |
Output is correct |
48 |
Correct |
8 ms |
860 KB |
Output is correct |
49 |
Correct |
7 ms |
860 KB |
Output is correct |
50 |
Correct |
10 ms |
1080 KB |
Output is correct |
51 |
Correct |
10 ms |
1580 KB |
Output is correct |
52 |
Correct |
13 ms |
4184 KB |
Output is correct |
53 |
Correct |
13 ms |
6744 KB |
Output is correct |
54 |
Correct |
11 ms |
4188 KB |
Output is correct |
55 |
Correct |
12 ms |
3932 KB |
Output is correct |
56 |
Correct |
6 ms |
604 KB |
Output is correct |
57 |
Correct |
7 ms |
600 KB |
Output is correct |
58 |
Correct |
9 ms |
856 KB |
Output is correct |
59 |
Correct |
1054 ms |
13896 KB |
Output is correct |
60 |
Correct |
1265 ms |
23592 KB |
Output is correct |
61 |
Correct |
1345 ms |
29628 KB |
Output is correct |
62 |
Correct |
1280 ms |
22808 KB |
Output is correct |
63 |
Correct |
1245 ms |
23728 KB |
Output is correct |
64 |
Correct |
1244 ms |
23396 KB |
Output is correct |
65 |
Correct |
1252 ms |
23120 KB |
Output is correct |
66 |
Correct |
871 ms |
10072 KB |
Output is correct |
67 |
Correct |
1086 ms |
18332 KB |
Output is correct |
68 |
Correct |
1204 ms |
19568 KB |
Output is correct |
69 |
Correct |
1112 ms |
18808 KB |
Output is correct |
70 |
Correct |
1105 ms |
18464 KB |
Output is correct |
71 |
Correct |
1082 ms |
18404 KB |
Output is correct |
72 |
Correct |
1136 ms |
18728 KB |
Output is correct |
73 |
Correct |
4 ms |
2396 KB |
Output is correct |
74 |
Correct |
4 ms |
1628 KB |
Output is correct |
75 |
Correct |
480 ms |
6256 KB |
Output is correct |
76 |
Correct |
621 ms |
6784 KB |
Output is correct |
77 |
Correct |
1536 ms |
12264 KB |
Output is correct |
78 |
Correct |
1382 ms |
13420 KB |
Output is correct |
79 |
Correct |
1412 ms |
13548 KB |
Output is correct |
80 |
Correct |
1421 ms |
72020 KB |
Output is correct |
81 |
Correct |
1502 ms |
110124 KB |
Output is correct |
82 |
Correct |
1771 ms |
333488 KB |
Output is correct |
83 |
Correct |
2023 ms |
515188 KB |
Output is correct |
84 |
Correct |
1643 ms |
380240 KB |
Output is correct |
85 |
Correct |
1733 ms |
379488 KB |
Output is correct |
86 |
Correct |
873 ms |
10680 KB |
Output is correct |
87 |
Correct |
871 ms |
10832 KB |
Output is correct |
88 |
Correct |
956 ms |
11248 KB |
Output is correct |
89 |
Correct |
1078 ms |
40020 KB |
Output is correct |
90 |
Correct |
1094 ms |
16392 KB |
Output is correct |
91 |
Correct |
1608 ms |
50976 KB |
Output is correct |
92 |
Correct |
1655 ms |
53840 KB |
Output is correct |
93 |
Correct |
1591 ms |
48976 KB |
Output is correct |
94 |
Correct |
1603 ms |
48812 KB |
Output is correct |
95 |
Correct |
1596 ms |
50624 KB |
Output is correct |
96 |
Correct |
1604 ms |
48996 KB |
Output is correct |
97 |
Correct |
889 ms |
12184 KB |
Output is correct |
98 |
Correct |
1450 ms |
43728 KB |
Output is correct |
99 |
Correct |
1524 ms |
45652 KB |
Output is correct |
100 |
Correct |
1487 ms |
44276 KB |
Output is correct |
101 |
Correct |
1452 ms |
43484 KB |
Output is correct |
102 |
Correct |
1456 ms |
43580 KB |
Output is correct |
103 |
Correct |
1499 ms |
44116 KB |
Output is correct |
104 |
Correct |
820 ms |
30820 KB |
Output is correct |
105 |
Correct |
1034 ms |
33872 KB |
Output is correct |
106 |
Correct |
1885 ms |
42832 KB |
Output is correct |
107 |
Correct |
1788 ms |
42000 KB |
Output is correct |
108 |
Correct |
1802 ms |
42492 KB |
Output is correct |
109 |
Correct |
1745 ms |
42064 KB |
Output is correct |
110 |
Correct |
1798 ms |
42340 KB |
Output is correct |
111 |
Correct |
1746 ms |
97580 KB |
Output is correct |
112 |
Correct |
1858 ms |
136716 KB |
Output is correct |
113 |
Correct |
2501 ms |
417684 KB |
Output is correct |
114 |
Correct |
3336 ms |
376700 KB |
Output is correct |
115 |
Correct |
2396 ms |
347616 KB |
Output is correct |
116 |
Correct |
2124 ms |
381620 KB |
Output is correct |
117 |
Correct |
1225 ms |
38484 KB |
Output is correct |
118 |
Correct |
1342 ms |
39252 KB |
Output is correct |
119 |
Correct |
1296 ms |
37828 KB |
Output is correct |
120 |
Correct |
1435 ms |
39860 KB |
Output is correct |
121 |
Correct |
1359 ms |
40424 KB |
Output is correct |
122 |
Correct |
1630 ms |
62088 KB |
Output is correct |
123 |
Correct |
3398 ms |
376512 KB |
Output is correct |
124 |
Correct |
3415 ms |
314228 KB |
Output is correct |
125 |
Correct |
3372 ms |
284720 KB |
Output is correct |