#include <bits/stdc++.h>
typedef long long ll;
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
struct tim{
ll time,exp,i;
void log(){
cout<<"{ "<<time<<" , "<<exp<<" , "<<i<<" } ";
}
};
bool operator>(tim c, tim b){
return c.time > b.time;
}
bool operator<(tim c, tim b){
return c.time < b.time;
}
tim mxtm(tim a,tim b){
if(a.exp >= b.exp) return a;
else return b;
}
int n;
struct lst{
vector<tim>v;
tim seg[4001];
void update(int ind,tim val){
ind += n;
seg[ind] = val;
ind /= 2;
while(ind){
seg[ind] = mxtm(seg[ind * 2],seg[ind * 2 + 1]);
ind /= 2;
}
}
tim query(int l,int r,int s,int e,int ind){
if(l > e || r < s) return {-1,-1,-1};
if(l >= s && r <= e) return seg[ind];
int md = (l + r) / 2;
return mxtm(query(l,md,s,e,ind * 2),query(md + 1,r,s,e,ind * 2 + 1));
}
void build(){
for(int i = 0;i < v.size();i++){
update(i,v[i]);
}
}
ll find(tim a){
ll x = lower_bound(v.begin(),v.end(),a) - v.begin();
x--;
// cout<<x<<' ';a.log();
// cout<<'\n';
if(x == -1){
return a.exp;
}
auto ans = query(1,n,1,x + 1,1);
return max(a.exp,ans.exp);
}
};
lst a[4001];
ll x;
ll m;
ll n1;
vector<int>s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
m = M;
x = ll(X);
s = S;
n = exp2(ceil(log2(N)));
n1 = n;
for(int i = 0;i < N;i++){
a[0].v.push_back({T[i],ll(T[i] + ll((ll)(S[1] - S[0]) * (ll)W[i])),i});
}
sort(a[0].v.begin(),a[0].v.end());
a[0].build();
for(ll i = 1;i < M - 1;i++){
ll mx = 0;
ll prev = -1;
queue<ll>q;
for(auto x : a[i - 1].v){
if(x.time != prev){
while(q.size()){
mx = max(mx,q.front());
q.pop();
}
}
q.push(x.exp);
prev = x.time;
ll t = max(mx,x.exp);
ll id = x.i;
ll e = ll(t + (ll)((ll)(S[i + 1] - S[i]) * (ll)(W[id])));
a[i].v.push_back({t,e,id});
}
sort(a[i].v.begin(),a[i].v.end());
a[i].build();
}
// for(int i = 0;i < M - 1;i++){
// for(auto x : a[i].v){
// x.log();
// }
// cout<<'\n';
// }
}
long long arrival_time(long long Y)
{
tim ans = {Y,(ll)(Y + (ll)((ll)(s[1] - s[0]) * (ll)x)),n1};
for(ll i = 1;i < m;i++){
// ans.log();
ll mx = max(a[i-1].find(ans),ans.exp);
if(i == m - 1) return mx;
ans = {mx,mx + (ll)(s[i + 1] - s[i]) * (ll)x,n1};
}
}
//
// int main()
// {
// int L, N, X, M, Q;
// assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
// std::vector<long long> T(N);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%lld", &T[i]));
// std::vector<int> W(N);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &W[i]));
// std::vector<int> S(M);
// for (int i = 0; i < M; i++)
// assert(1 == scanf("%d", &S[i]));
// std::vector<long long> Y(Q);
// for (int i = 0; i < Q; i++)
// assert(1 == scanf("%lld", &Y[i]));
//
// fclose(stdin);
//
// init(L, N, T, W, X, M, S);
// std::vector<long long> res(Q);
// for (int i = 0; i < Q; i++)
// res[i] = arrival_time(Y[i]);
//
// for (int i = 0; i < Q; i++)
// printf("%lld\n", res[i]);
// fclose(stdout);
// return 0;
// }
Compilation message
overtaking.cpp: In member function 'void lst::build()':
overtaking.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tim>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0;i < v.size();i++){
| ~~^~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
115 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
375876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
375920 KB |
Output is correct |
2 |
Correct |
35 ms |
375892 KB |
Output is correct |
3 |
Correct |
35 ms |
375768 KB |
Output is correct |
4 |
Correct |
35 ms |
375888 KB |
Output is correct |
5 |
Correct |
35 ms |
375888 KB |
Output is correct |
6 |
Correct |
37 ms |
375892 KB |
Output is correct |
7 |
Correct |
38 ms |
376088 KB |
Output is correct |
8 |
Correct |
44 ms |
375828 KB |
Output is correct |
9 |
Correct |
39 ms |
375892 KB |
Output is correct |
10 |
Correct |
40 ms |
375892 KB |
Output is correct |
11 |
Correct |
44 ms |
375888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
375888 KB |
Output is correct |
2 |
Correct |
36 ms |
375860 KB |
Output is correct |
3 |
Correct |
35 ms |
375888 KB |
Output is correct |
4 |
Correct |
37 ms |
375892 KB |
Output is correct |
5 |
Correct |
35 ms |
375908 KB |
Output is correct |
6 |
Correct |
35 ms |
375960 KB |
Output is correct |
7 |
Correct |
36 ms |
376036 KB |
Output is correct |
8 |
Correct |
36 ms |
375888 KB |
Output is correct |
9 |
Correct |
36 ms |
375952 KB |
Output is correct |
10 |
Correct |
35 ms |
375900 KB |
Output is correct |
11 |
Correct |
35 ms |
375900 KB |
Output is correct |
12 |
Correct |
36 ms |
376040 KB |
Output is correct |
13 |
Correct |
35 ms |
375996 KB |
Output is correct |
14 |
Correct |
36 ms |
375892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
375876 KB |
Output is correct |
2 |
Correct |
37 ms |
375920 KB |
Output is correct |
3 |
Correct |
35 ms |
375892 KB |
Output is correct |
4 |
Correct |
35 ms |
375768 KB |
Output is correct |
5 |
Correct |
35 ms |
375888 KB |
Output is correct |
6 |
Correct |
35 ms |
375888 KB |
Output is correct |
7 |
Correct |
36 ms |
375860 KB |
Output is correct |
8 |
Correct |
35 ms |
375888 KB |
Output is correct |
9 |
Correct |
36 ms |
376068 KB |
Output is correct |
10 |
Correct |
36 ms |
376144 KB |
Output is correct |
11 |
Correct |
35 ms |
376144 KB |
Output is correct |
12 |
Correct |
38 ms |
376168 KB |
Output is correct |
13 |
Correct |
36 ms |
376028 KB |
Output is correct |
14 |
Correct |
38 ms |
376148 KB |
Output is correct |
15 |
Correct |
39 ms |
376144 KB |
Output is correct |
16 |
Correct |
38 ms |
376156 KB |
Output is correct |
17 |
Correct |
36 ms |
376148 KB |
Output is correct |
18 |
Correct |
37 ms |
376276 KB |
Output is correct |
19 |
Correct |
37 ms |
376156 KB |
Output is correct |
20 |
Correct |
38 ms |
376248 KB |
Output is correct |
21 |
Correct |
38 ms |
376108 KB |
Output is correct |
22 |
Correct |
36 ms |
375892 KB |
Output is correct |
23 |
Correct |
38 ms |
376148 KB |
Output is correct |
24 |
Correct |
37 ms |
376180 KB |
Output is correct |
25 |
Correct |
38 ms |
376168 KB |
Output is correct |
26 |
Correct |
38 ms |
376200 KB |
Output is correct |
27 |
Correct |
38 ms |
376156 KB |
Output is correct |
28 |
Correct |
36 ms |
376092 KB |
Output is correct |
29 |
Correct |
38 ms |
376144 KB |
Output is correct |
30 |
Correct |
36 ms |
376144 KB |
Output is correct |
31 |
Correct |
36 ms |
376144 KB |
Output is correct |
32 |
Correct |
37 ms |
376044 KB |
Output is correct |
33 |
Correct |
36 ms |
376152 KB |
Output is correct |
34 |
Correct |
37 ms |
376180 KB |
Output is correct |
35 |
Correct |
37 ms |
376148 KB |
Output is correct |
36 |
Correct |
37 ms |
376144 KB |
Output is correct |
37 |
Correct |
35 ms |
376252 KB |
Output is correct |
38 |
Correct |
36 ms |
376144 KB |
Output is correct |
39 |
Correct |
37 ms |
376184 KB |
Output is correct |
40 |
Correct |
39 ms |
376144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
375876 KB |
Output is correct |
2 |
Correct |
37 ms |
375920 KB |
Output is correct |
3 |
Correct |
35 ms |
375892 KB |
Output is correct |
4 |
Correct |
35 ms |
375768 KB |
Output is correct |
5 |
Correct |
35 ms |
375888 KB |
Output is correct |
6 |
Correct |
35 ms |
375888 KB |
Output is correct |
7 |
Correct |
37 ms |
375892 KB |
Output is correct |
8 |
Correct |
38 ms |
376088 KB |
Output is correct |
9 |
Correct |
44 ms |
375828 KB |
Output is correct |
10 |
Correct |
39 ms |
375892 KB |
Output is correct |
11 |
Correct |
40 ms |
375892 KB |
Output is correct |
12 |
Correct |
44 ms |
375888 KB |
Output is correct |
13 |
Correct |
35 ms |
375888 KB |
Output is correct |
14 |
Correct |
36 ms |
375860 KB |
Output is correct |
15 |
Correct |
35 ms |
375888 KB |
Output is correct |
16 |
Correct |
36 ms |
376068 KB |
Output is correct |
17 |
Correct |
36 ms |
376144 KB |
Output is correct |
18 |
Correct |
35 ms |
376144 KB |
Output is correct |
19 |
Correct |
38 ms |
376168 KB |
Output is correct |
20 |
Correct |
36 ms |
376028 KB |
Output is correct |
21 |
Correct |
38 ms |
376148 KB |
Output is correct |
22 |
Correct |
39 ms |
376144 KB |
Output is correct |
23 |
Correct |
38 ms |
376156 KB |
Output is correct |
24 |
Correct |
36 ms |
376148 KB |
Output is correct |
25 |
Correct |
37 ms |
376276 KB |
Output is correct |
26 |
Correct |
37 ms |
376156 KB |
Output is correct |
27 |
Correct |
38 ms |
376248 KB |
Output is correct |
28 |
Correct |
38 ms |
376108 KB |
Output is correct |
29 |
Correct |
36 ms |
375892 KB |
Output is correct |
30 |
Correct |
38 ms |
376148 KB |
Output is correct |
31 |
Correct |
37 ms |
376180 KB |
Output is correct |
32 |
Correct |
38 ms |
376168 KB |
Output is correct |
33 |
Correct |
38 ms |
376200 KB |
Output is correct |
34 |
Correct |
38 ms |
376156 KB |
Output is correct |
35 |
Correct |
36 ms |
376092 KB |
Output is correct |
36 |
Correct |
38 ms |
376144 KB |
Output is correct |
37 |
Correct |
36 ms |
376144 KB |
Output is correct |
38 |
Correct |
36 ms |
376144 KB |
Output is correct |
39 |
Correct |
37 ms |
376044 KB |
Output is correct |
40 |
Correct |
36 ms |
376152 KB |
Output is correct |
41 |
Correct |
37 ms |
376180 KB |
Output is correct |
42 |
Correct |
37 ms |
376148 KB |
Output is correct |
43 |
Correct |
37 ms |
376144 KB |
Output is correct |
44 |
Correct |
35 ms |
376252 KB |
Output is correct |
45 |
Correct |
36 ms |
376144 KB |
Output is correct |
46 |
Correct |
37 ms |
376184 KB |
Output is correct |
47 |
Correct |
39 ms |
376144 KB |
Output is correct |
48 |
Correct |
288 ms |
400160 KB |
Output is correct |
49 |
Correct |
814 ms |
400232 KB |
Output is correct |
50 |
Correct |
800 ms |
400232 KB |
Output is correct |
51 |
Correct |
797 ms |
400232 KB |
Output is correct |
52 |
Correct |
812 ms |
400232 KB |
Output is correct |
53 |
Correct |
758 ms |
400228 KB |
Output is correct |
54 |
Correct |
838 ms |
400232 KB |
Output is correct |
55 |
Correct |
246 ms |
400160 KB |
Output is correct |
56 |
Correct |
737 ms |
400232 KB |
Output is correct |
57 |
Correct |
762 ms |
400232 KB |
Output is correct |
58 |
Correct |
763 ms |
400232 KB |
Output is correct |
59 |
Correct |
788 ms |
400460 KB |
Output is correct |
60 |
Correct |
753 ms |
400360 KB |
Output is correct |
61 |
Correct |
785 ms |
400228 KB |
Output is correct |
62 |
Correct |
53 ms |
376032 KB |
Output is correct |
63 |
Correct |
37 ms |
376140 KB |
Output is correct |
64 |
Correct |
857 ms |
388144 KB |
Output is correct |
65 |
Correct |
783 ms |
388196 KB |
Output is correct |
66 |
Correct |
1542 ms |
400232 KB |
Output is correct |
67 |
Correct |
1727 ms |
400232 KB |
Output is correct |
68 |
Correct |
1735 ms |
400232 KB |
Output is correct |
69 |
Correct |
1646 ms |
400236 KB |
Output is correct |
70 |
Correct |
1678 ms |
400228 KB |
Output is correct |
71 |
Correct |
1613 ms |
400236 KB |
Output is correct |
72 |
Correct |
1624 ms |
400232 KB |
Output is correct |
73 |
Correct |
1800 ms |
400228 KB |
Output is correct |
74 |
Correct |
1668 ms |
400232 KB |
Output is correct |
75 |
Correct |
1550 ms |
400236 KB |
Output is correct |
76 |
Correct |
1492 ms |
400256 KB |
Output is correct |
77 |
Correct |
1716 ms |
400196 KB |
Output is correct |
78 |
Correct |
652 ms |
400236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
375876 KB |
Output is correct |
2 |
Correct |
37 ms |
375920 KB |
Output is correct |
3 |
Correct |
35 ms |
375892 KB |
Output is correct |
4 |
Correct |
35 ms |
375768 KB |
Output is correct |
5 |
Correct |
35 ms |
375888 KB |
Output is correct |
6 |
Correct |
35 ms |
375888 KB |
Output is correct |
7 |
Correct |
37 ms |
375892 KB |
Output is correct |
8 |
Correct |
38 ms |
376088 KB |
Output is correct |
9 |
Correct |
44 ms |
375828 KB |
Output is correct |
10 |
Correct |
39 ms |
375892 KB |
Output is correct |
11 |
Correct |
40 ms |
375892 KB |
Output is correct |
12 |
Correct |
44 ms |
375888 KB |
Output is correct |
13 |
Correct |
35 ms |
375888 KB |
Output is correct |
14 |
Correct |
36 ms |
375860 KB |
Output is correct |
15 |
Correct |
35 ms |
375888 KB |
Output is correct |
16 |
Correct |
37 ms |
375892 KB |
Output is correct |
17 |
Correct |
35 ms |
375908 KB |
Output is correct |
18 |
Correct |
35 ms |
375960 KB |
Output is correct |
19 |
Correct |
36 ms |
376036 KB |
Output is correct |
20 |
Correct |
36 ms |
375888 KB |
Output is correct |
21 |
Correct |
36 ms |
375952 KB |
Output is correct |
22 |
Correct |
35 ms |
375900 KB |
Output is correct |
23 |
Correct |
35 ms |
375900 KB |
Output is correct |
24 |
Correct |
36 ms |
376040 KB |
Output is correct |
25 |
Correct |
35 ms |
375996 KB |
Output is correct |
26 |
Correct |
36 ms |
375892 KB |
Output is correct |
27 |
Correct |
36 ms |
376068 KB |
Output is correct |
28 |
Correct |
36 ms |
376144 KB |
Output is correct |
29 |
Correct |
35 ms |
376144 KB |
Output is correct |
30 |
Correct |
38 ms |
376168 KB |
Output is correct |
31 |
Correct |
36 ms |
376028 KB |
Output is correct |
32 |
Correct |
38 ms |
376148 KB |
Output is correct |
33 |
Correct |
39 ms |
376144 KB |
Output is correct |
34 |
Correct |
38 ms |
376156 KB |
Output is correct |
35 |
Correct |
36 ms |
376148 KB |
Output is correct |
36 |
Correct |
37 ms |
376276 KB |
Output is correct |
37 |
Correct |
37 ms |
376156 KB |
Output is correct |
38 |
Correct |
38 ms |
376248 KB |
Output is correct |
39 |
Correct |
38 ms |
376108 KB |
Output is correct |
40 |
Correct |
36 ms |
375892 KB |
Output is correct |
41 |
Correct |
38 ms |
376148 KB |
Output is correct |
42 |
Correct |
37 ms |
376180 KB |
Output is correct |
43 |
Correct |
38 ms |
376168 KB |
Output is correct |
44 |
Correct |
38 ms |
376200 KB |
Output is correct |
45 |
Correct |
38 ms |
376156 KB |
Output is correct |
46 |
Correct |
36 ms |
376092 KB |
Output is correct |
47 |
Correct |
38 ms |
376144 KB |
Output is correct |
48 |
Correct |
36 ms |
376144 KB |
Output is correct |
49 |
Correct |
36 ms |
376144 KB |
Output is correct |
50 |
Correct |
37 ms |
376044 KB |
Output is correct |
51 |
Correct |
36 ms |
376152 KB |
Output is correct |
52 |
Correct |
37 ms |
376180 KB |
Output is correct |
53 |
Correct |
37 ms |
376148 KB |
Output is correct |
54 |
Correct |
37 ms |
376144 KB |
Output is correct |
55 |
Correct |
35 ms |
376252 KB |
Output is correct |
56 |
Correct |
36 ms |
376144 KB |
Output is correct |
57 |
Correct |
37 ms |
376184 KB |
Output is correct |
58 |
Correct |
39 ms |
376144 KB |
Output is correct |
59 |
Correct |
288 ms |
400160 KB |
Output is correct |
60 |
Correct |
814 ms |
400232 KB |
Output is correct |
61 |
Correct |
800 ms |
400232 KB |
Output is correct |
62 |
Correct |
797 ms |
400232 KB |
Output is correct |
63 |
Correct |
812 ms |
400232 KB |
Output is correct |
64 |
Correct |
758 ms |
400228 KB |
Output is correct |
65 |
Correct |
838 ms |
400232 KB |
Output is correct |
66 |
Correct |
246 ms |
400160 KB |
Output is correct |
67 |
Correct |
737 ms |
400232 KB |
Output is correct |
68 |
Correct |
762 ms |
400232 KB |
Output is correct |
69 |
Correct |
763 ms |
400232 KB |
Output is correct |
70 |
Correct |
788 ms |
400460 KB |
Output is correct |
71 |
Correct |
753 ms |
400360 KB |
Output is correct |
72 |
Correct |
785 ms |
400228 KB |
Output is correct |
73 |
Correct |
53 ms |
376032 KB |
Output is correct |
74 |
Correct |
37 ms |
376140 KB |
Output is correct |
75 |
Correct |
857 ms |
388144 KB |
Output is correct |
76 |
Correct |
783 ms |
388196 KB |
Output is correct |
77 |
Correct |
1542 ms |
400232 KB |
Output is correct |
78 |
Correct |
1727 ms |
400232 KB |
Output is correct |
79 |
Correct |
1735 ms |
400232 KB |
Output is correct |
80 |
Correct |
1646 ms |
400236 KB |
Output is correct |
81 |
Correct |
1678 ms |
400228 KB |
Output is correct |
82 |
Correct |
1613 ms |
400236 KB |
Output is correct |
83 |
Correct |
1624 ms |
400232 KB |
Output is correct |
84 |
Correct |
1800 ms |
400228 KB |
Output is correct |
85 |
Correct |
1668 ms |
400232 KB |
Output is correct |
86 |
Correct |
1550 ms |
400236 KB |
Output is correct |
87 |
Correct |
1492 ms |
400256 KB |
Output is correct |
88 |
Correct |
1716 ms |
400196 KB |
Output is correct |
89 |
Correct |
652 ms |
400236 KB |
Output is correct |
90 |
Execution timed out |
3543 ms |
401884 KB |
Time limit exceeded |
91 |
Halted |
0 ms |
0 KB |
- |