#include "overtaking.h"
#include <bits/stdc++.h>
#define MAXN 1007
using namespace std;
long long l,x;
vector<long long> t,w,s,poz[MAXN];
vector<int> koji[MAXN];
int n,m;
map<pair<int,long long> ,long long> mp;
int manjih(long long val,int ind)
{
if(n==0) return 0;
if(poz[ind][0]>=val) return 0;
int l=0,r=n-1;
while(l!=r)
{
int sr=(l+r+1)/2;
if(poz[ind][sr]<val) l=sr;
else r=sr-1;
}
return l+1;}
pair<int,long long> next(int stan, long long vreme)
{
int br=manjih(vreme,stan);
if(manjih(vreme+x*(l-s[stan]),m-1)==br) return {m-1,vreme+x*(l-s[stan])};
int l=stan+1,r=m-1;
while(l!=r)
{
int sr=(l+r)/2;
long long novo=vreme+x*(s[sr]-s[stan]);
if(manjih(novo,sr)!=br) r=sr;
else l=sr+1;
}
return {l,poz[l][br-1]};
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l=L; x=X; m=M; n=N;
for(int i=0;i<M;i++) s.push_back(S[i]);
for(int i=0;i<N;i++)
{
if(W[i]<X) n--;
else
{
w.push_back(W[i]);
t.push_back(T[i]);
}
}
vector<pair<long long,int>> zs;
for(int i=0;i<n;i++) zs.push_back({t[i],i});
sort(zs.begin(),zs.end());
for(int i=0;i<n;i++) poz[0].push_back(zs[i].first);
for(int i=0;i<n;i++) koji[0].push_back(zs[i].second);
for(int j=1;j<m;j++)
{
vector<pair<long long,int> > v;
long long tmax=0,cmax=0;
for(int i=0;i<n;i++)
{
if(i!=0 && poz[j-1][i]!=poz[j-1][i-1]) cmax=tmax;
long long ar=poz[j-1][i]+w[koji[j-1][i]]*(s[j]-s[j-1]);
tmax=max(tmax,ar);
v.push_back({max(ar,cmax),koji[j-1][i]});
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++) poz[j].push_back(v[i].first);
for(int i=0;i<n;i++) koji[j].push_back(v[i].second);
}
for(int j=m-1;j>=0;j--) for(int i=0;i<n;i++)
{
pair<int,long long> pill=next(j,poz[j][i]);
if(pill.first==m-1) mp[{j,poz[j][i]}]=pill.second;
else mp[{j,poz[j][i]}]=mp[pill];
}
return;
}
long long arrival_time(long long Y)
{
pair<int,long long> pill=next(0,Y);
if(pill.first==m-1) return pill.second;
else return mp[pill];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 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 |
344 KB |
Output is correct |
9 |
Correct |
4 ms |
1116 KB |
Output is correct |
10 |
Correct |
3 ms |
1116 KB |
Output is correct |
11 |
Correct |
4 ms |
1112 KB |
Output is correct |
12 |
Correct |
4 ms |
1116 KB |
Output is correct |
13 |
Correct |
3 ms |
1112 KB |
Output is correct |
14 |
Correct |
4 ms |
1116 KB |
Output is correct |
15 |
Correct |
7 ms |
1116 KB |
Output is correct |
16 |
Correct |
4 ms |
1112 KB |
Output is correct |
17 |
Correct |
6 ms |
1112 KB |
Output is correct |
18 |
Correct |
5 ms |
1116 KB |
Output is correct |
19 |
Correct |
6 ms |
1112 KB |
Output is correct |
20 |
Correct |
4 ms |
1112 KB |
Output is correct |
21 |
Correct |
3 ms |
860 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
23 |
Correct |
4 ms |
856 KB |
Output is correct |
24 |
Correct |
4 ms |
860 KB |
Output is correct |
25 |
Correct |
5 ms |
860 KB |
Output is correct |
26 |
Correct |
4 ms |
860 KB |
Output is correct |
27 |
Correct |
4 ms |
1112 KB |
Output is correct |
28 |
Correct |
3 ms |
856 KB |
Output is correct |
29 |
Correct |
3 ms |
856 KB |
Output is correct |
30 |
Correct |
4 ms |
860 KB |
Output is correct |
31 |
Correct |
3 ms |
856 KB |
Output is correct |
32 |
Correct |
2 ms |
1112 KB |
Output is correct |
33 |
Correct |
2 ms |
1116 KB |
Output is correct |
34 |
Correct |
3 ms |
1112 KB |
Output is correct |
35 |
Correct |
2 ms |
1112 KB |
Output is correct |
36 |
Correct |
2 ms |
1112 KB |
Output is correct |
37 |
Correct |
3 ms |
1112 KB |
Output is correct |
38 |
Correct |
0 ms |
344 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
4 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 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 |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
1116 KB |
Output is correct |
17 |
Correct |
3 ms |
1116 KB |
Output is correct |
18 |
Correct |
4 ms |
1112 KB |
Output is correct |
19 |
Correct |
4 ms |
1116 KB |
Output is correct |
20 |
Correct |
3 ms |
1112 KB |
Output is correct |
21 |
Correct |
4 ms |
1116 KB |
Output is correct |
22 |
Correct |
7 ms |
1116 KB |
Output is correct |
23 |
Correct |
4 ms |
1112 KB |
Output is correct |
24 |
Correct |
6 ms |
1112 KB |
Output is correct |
25 |
Correct |
5 ms |
1116 KB |
Output is correct |
26 |
Correct |
6 ms |
1112 KB |
Output is correct |
27 |
Correct |
4 ms |
1112 KB |
Output is correct |
28 |
Correct |
3 ms |
860 KB |
Output is correct |
29 |
Correct |
3 ms |
604 KB |
Output is correct |
30 |
Correct |
4 ms |
856 KB |
Output is correct |
31 |
Correct |
4 ms |
860 KB |
Output is correct |
32 |
Correct |
5 ms |
860 KB |
Output is correct |
33 |
Correct |
4 ms |
860 KB |
Output is correct |
34 |
Correct |
4 ms |
1112 KB |
Output is correct |
35 |
Correct |
3 ms |
856 KB |
Output is correct |
36 |
Correct |
3 ms |
856 KB |
Output is correct |
37 |
Correct |
4 ms |
860 KB |
Output is correct |
38 |
Correct |
3 ms |
856 KB |
Output is correct |
39 |
Correct |
2 ms |
1112 KB |
Output is correct |
40 |
Correct |
2 ms |
1116 KB |
Output is correct |
41 |
Correct |
3 ms |
1112 KB |
Output is correct |
42 |
Correct |
2 ms |
1112 KB |
Output is correct |
43 |
Correct |
2 ms |
1112 KB |
Output is correct |
44 |
Correct |
3 ms |
1112 KB |
Output is correct |
45 |
Correct |
0 ms |
344 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
4 ms |
1116 KB |
Output is correct |
48 |
Correct |
914 ms |
72408 KB |
Output is correct |
49 |
Correct |
933 ms |
72496 KB |
Output is correct |
50 |
Correct |
932 ms |
74036 KB |
Output is correct |
51 |
Correct |
904 ms |
72280 KB |
Output is correct |
52 |
Correct |
874 ms |
72708 KB |
Output is correct |
53 |
Correct |
906 ms |
72356 KB |
Output is correct |
54 |
Correct |
911 ms |
72452 KB |
Output is correct |
55 |
Correct |
635 ms |
51068 KB |
Output is correct |
56 |
Correct |
747 ms |
72028 KB |
Output is correct |
57 |
Correct |
728 ms |
68436 KB |
Output is correct |
58 |
Correct |
797 ms |
73172 KB |
Output is correct |
59 |
Correct |
822 ms |
72164 KB |
Output is correct |
60 |
Correct |
747 ms |
72016 KB |
Output is correct |
61 |
Correct |
761 ms |
72808 KB |
Output is correct |
62 |
Correct |
3 ms |
600 KB |
Output is correct |
63 |
Correct |
2 ms |
600 KB |
Output is correct |
64 |
Correct |
381 ms |
35704 KB |
Output is correct |
65 |
Correct |
380 ms |
35152 KB |
Output is correct |
66 |
Correct |
788 ms |
69540 KB |
Output is correct |
67 |
Correct |
801 ms |
70872 KB |
Output is correct |
68 |
Correct |
789 ms |
70464 KB |
Output is correct |
69 |
Correct |
332 ms |
75344 KB |
Output is correct |
70 |
Correct |
333 ms |
75088 KB |
Output is correct |
71 |
Correct |
342 ms |
75188 KB |
Output is correct |
72 |
Correct |
604 ms |
75284 KB |
Output is correct |
73 |
Correct |
343 ms |
75344 KB |
Output is correct |
74 |
Correct |
347 ms |
75288 KB |
Output is correct |
75 |
Correct |
1 ms |
600 KB |
Output is correct |
76 |
Correct |
1 ms |
600 KB |
Output is correct |
77 |
Correct |
1 ms |
600 KB |
Output is correct |
78 |
Correct |
675 ms |
75284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 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 |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
600 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
4 ms |
1116 KB |
Output is correct |
28 |
Correct |
3 ms |
1116 KB |
Output is correct |
29 |
Correct |
4 ms |
1112 KB |
Output is correct |
30 |
Correct |
4 ms |
1116 KB |
Output is correct |
31 |
Correct |
3 ms |
1112 KB |
Output is correct |
32 |
Correct |
4 ms |
1116 KB |
Output is correct |
33 |
Correct |
7 ms |
1116 KB |
Output is correct |
34 |
Correct |
4 ms |
1112 KB |
Output is correct |
35 |
Correct |
6 ms |
1112 KB |
Output is correct |
36 |
Correct |
5 ms |
1116 KB |
Output is correct |
37 |
Correct |
6 ms |
1112 KB |
Output is correct |
38 |
Correct |
4 ms |
1112 KB |
Output is correct |
39 |
Correct |
3 ms |
860 KB |
Output is correct |
40 |
Correct |
3 ms |
604 KB |
Output is correct |
41 |
Correct |
4 ms |
856 KB |
Output is correct |
42 |
Correct |
4 ms |
860 KB |
Output is correct |
43 |
Correct |
5 ms |
860 KB |
Output is correct |
44 |
Correct |
4 ms |
860 KB |
Output is correct |
45 |
Correct |
4 ms |
1112 KB |
Output is correct |
46 |
Correct |
3 ms |
856 KB |
Output is correct |
47 |
Correct |
3 ms |
856 KB |
Output is correct |
48 |
Correct |
4 ms |
860 KB |
Output is correct |
49 |
Correct |
3 ms |
856 KB |
Output is correct |
50 |
Correct |
2 ms |
1112 KB |
Output is correct |
51 |
Correct |
2 ms |
1116 KB |
Output is correct |
52 |
Correct |
3 ms |
1112 KB |
Output is correct |
53 |
Correct |
2 ms |
1112 KB |
Output is correct |
54 |
Correct |
2 ms |
1112 KB |
Output is correct |
55 |
Correct |
3 ms |
1112 KB |
Output is correct |
56 |
Correct |
0 ms |
344 KB |
Output is correct |
57 |
Correct |
0 ms |
344 KB |
Output is correct |
58 |
Correct |
4 ms |
1116 KB |
Output is correct |
59 |
Correct |
914 ms |
72408 KB |
Output is correct |
60 |
Correct |
933 ms |
72496 KB |
Output is correct |
61 |
Correct |
932 ms |
74036 KB |
Output is correct |
62 |
Correct |
904 ms |
72280 KB |
Output is correct |
63 |
Correct |
874 ms |
72708 KB |
Output is correct |
64 |
Correct |
906 ms |
72356 KB |
Output is correct |
65 |
Correct |
911 ms |
72452 KB |
Output is correct |
66 |
Correct |
635 ms |
51068 KB |
Output is correct |
67 |
Correct |
747 ms |
72028 KB |
Output is correct |
68 |
Correct |
728 ms |
68436 KB |
Output is correct |
69 |
Correct |
797 ms |
73172 KB |
Output is correct |
70 |
Correct |
822 ms |
72164 KB |
Output is correct |
71 |
Correct |
747 ms |
72016 KB |
Output is correct |
72 |
Correct |
761 ms |
72808 KB |
Output is correct |
73 |
Correct |
3 ms |
600 KB |
Output is correct |
74 |
Correct |
2 ms |
600 KB |
Output is correct |
75 |
Correct |
381 ms |
35704 KB |
Output is correct |
76 |
Correct |
380 ms |
35152 KB |
Output is correct |
77 |
Correct |
788 ms |
69540 KB |
Output is correct |
78 |
Correct |
801 ms |
70872 KB |
Output is correct |
79 |
Correct |
789 ms |
70464 KB |
Output is correct |
80 |
Correct |
332 ms |
75344 KB |
Output is correct |
81 |
Correct |
333 ms |
75088 KB |
Output is correct |
82 |
Correct |
342 ms |
75188 KB |
Output is correct |
83 |
Correct |
604 ms |
75284 KB |
Output is correct |
84 |
Correct |
343 ms |
75344 KB |
Output is correct |
85 |
Correct |
347 ms |
75288 KB |
Output is correct |
86 |
Correct |
1 ms |
600 KB |
Output is correct |
87 |
Correct |
1 ms |
600 KB |
Output is correct |
88 |
Correct |
1 ms |
600 KB |
Output is correct |
89 |
Correct |
675 ms |
75284 KB |
Output is correct |
90 |
Correct |
972 ms |
73628 KB |
Output is correct |
91 |
Correct |
1623 ms |
97964 KB |
Output is correct |
92 |
Correct |
1762 ms |
99000 KB |
Output is correct |
93 |
Correct |
1643 ms |
98068 KB |
Output is correct |
94 |
Correct |
1718 ms |
98312 KB |
Output is correct |
95 |
Correct |
1626 ms |
98016 KB |
Output is correct |
96 |
Correct |
1615 ms |
98116 KB |
Output is correct |
97 |
Correct |
732 ms |
53544 KB |
Output is correct |
98 |
Correct |
1675 ms |
97284 KB |
Output is correct |
99 |
Correct |
1694 ms |
94052 KB |
Output is correct |
100 |
Correct |
1696 ms |
97656 KB |
Output is correct |
101 |
Correct |
1744 ms |
97104 KB |
Output is correct |
102 |
Correct |
1722 ms |
97512 KB |
Output is correct |
103 |
Correct |
1724 ms |
97512 KB |
Output is correct |
104 |
Correct |
1268 ms |
59836 KB |
Output is correct |
105 |
Correct |
1496 ms |
61596 KB |
Output is correct |
106 |
Correct |
1988 ms |
99688 KB |
Output is correct |
107 |
Correct |
2001 ms |
98364 KB |
Output is correct |
108 |
Correct |
1928 ms |
99308 KB |
Output is correct |
109 |
Correct |
1885 ms |
98456 KB |
Output is correct |
110 |
Correct |
1933 ms |
99608 KB |
Output is correct |
111 |
Correct |
636 ms |
100756 KB |
Output is correct |
112 |
Correct |
654 ms |
100924 KB |
Output is correct |
113 |
Correct |
1418 ms |
101692 KB |
Output is correct |
114 |
Correct |
2687 ms |
102916 KB |
Output is correct |
115 |
Correct |
1272 ms |
101888 KB |
Output is correct |
116 |
Correct |
730 ms |
101880 KB |
Output is correct |
117 |
Correct |
175 ms |
27984 KB |
Output is correct |
118 |
Correct |
179 ms |
27984 KB |
Output is correct |
119 |
Correct |
168 ms |
27216 KB |
Output is correct |
120 |
Correct |
178 ms |
28116 KB |
Output is correct |
121 |
Correct |
174 ms |
29008 KB |
Output is correct |
122 |
Correct |
1674 ms |
97792 KB |
Output is correct |
123 |
Correct |
2819 ms |
102916 KB |
Output is correct |
124 |
Correct |
2729 ms |
102904 KB |
Output is correct |
125 |
Correct |
2760 ms |
102904 KB |
Output is correct |