#include "overtaking.h"
#include <bits/stdc++.h>
#define MAX 1000001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
ll n,m,q,spd,road_len,b[1001],d[1001];
ll a[1001];
ll e[1001][1001];
vector<pll> g[1001];
ll p[1001][1001];
set<pll> v;
ll get_res(ll x){
pll p1=mp(x,INF);
auto it=v.upper_bound(p1);
if(it!=v.begin()){
--it;
x=max(x,(*it).ss);
}
return x;
}
void upd(ll x,ll y){
pll p1=mp(x,INF);
auto it=v.upper_bound(p1);
if(it!=v.begin() && (*(--it)).ss>=y){
return;
}
v.ins(mp(x,y));
it=v.upper_bound(p1);
while(it!=v.end() && (*it).ss<=y){
v.erase(*it);
it=v.upper_bound(p1);
}
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
road_len=L;
n=N;
spd=X;
m=M;
for(int i=0;i<n;i++){
a[i]=T[i];
}
// a avtobusların çıxma vaxtı üçün
for(int i=0;i<n;i++){
b[i]=W[i];
}
// b avtobusların sürətləri üçün
for(int i=0;i<m;i++){
d[i]=S[i];
}
// d stansiyalar üçün
// e stansiyalara çatma vaxtı üçün
// p g prefix max üçün
for(int i=0;i<n;i++){
e[i][0]=a[i];
}
for(int j=1;j<m;j++){
vector<pll> f; // avtobusların stansiyaya çatma vaxtına əsasən sıralayıb digər stansiyaya çatma vaxtını o(n)-ə hesablamaq üçün
for(int i=0;i<n;i++){
f.pb(mp(e[i][j-1],i));
}
sortv(f);
g[j-1]=f;
ll h=-1; // digər stansiyaya max çatma vaxtı
int z=0;
while(z<n){
int z1=z;
while(z1<n && f[z1].ff==f[z].ff){
e[f[z1].ss][j]=max(h,f[z1].ff+b[f[z1].ss]*(d[j]-d[j-1]));
z1++;
}
while(z<z1){
h=max(h,e[f[z].ss][j]);
z++;
}
}
}
vector<pll> f;
for(int i=0;i<n;i++){
f.pb(mp(e[i][m-1],i));
}
sortv(f);
g[m-1]=f;
for(int j=0;j<m;j++){
p[0][j]=g[j][0].ff;
for(int i=1;i<n;i++){
p[i][j]=max(p[i-1][j],g[j][i].ff);
}
}
for(int j=m-1;j>0;j--){
vector<pll> v1;
for(int i=0;i<n;i++){
v1.pb(mp(e[i][j-1],get_res(e[i][j]+(d[m-1]-d[j])*spd)));
}
for(auto x:v1){
upd(x.ff+1+(d[m-1]-d[j-1])*spd,x.ss);
}
}
return;
}
long long arrival_time(long long Y)
{
return get_res(Y+d[m-1]*spd);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2648 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2904 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
10840 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
15452 KB |
Output is correct |
8 |
Correct |
4 ms |
15452 KB |
Output is correct |
9 |
Correct |
3 ms |
15704 KB |
Output is correct |
10 |
Correct |
3 ms |
15448 KB |
Output is correct |
11 |
Correct |
3 ms |
15448 KB |
Output is correct |
12 |
Correct |
3 ms |
15448 KB |
Output is correct |
13 |
Correct |
3 ms |
15448 KB |
Output is correct |
14 |
Correct |
3 ms |
15448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
6 ms |
7000 KB |
Output is correct |
10 |
Correct |
5 ms |
7004 KB |
Output is correct |
11 |
Correct |
4 ms |
7256 KB |
Output is correct |
12 |
Correct |
5 ms |
7000 KB |
Output is correct |
13 |
Correct |
5 ms |
7000 KB |
Output is correct |
14 |
Correct |
4 ms |
7000 KB |
Output is correct |
15 |
Correct |
4 ms |
6744 KB |
Output is correct |
16 |
Correct |
4 ms |
6844 KB |
Output is correct |
17 |
Correct |
5 ms |
6744 KB |
Output is correct |
18 |
Correct |
4 ms |
6748 KB |
Output is correct |
19 |
Correct |
4 ms |
6744 KB |
Output is correct |
20 |
Correct |
4 ms |
7000 KB |
Output is correct |
21 |
Correct |
3 ms |
4696 KB |
Output is correct |
22 |
Correct |
2 ms |
6744 KB |
Output is correct |
23 |
Correct |
3 ms |
6744 KB |
Output is correct |
24 |
Correct |
3 ms |
6744 KB |
Output is correct |
25 |
Correct |
4 ms |
6744 KB |
Output is correct |
26 |
Correct |
4 ms |
6744 KB |
Output is correct |
27 |
Correct |
4 ms |
7000 KB |
Output is correct |
28 |
Correct |
3 ms |
6744 KB |
Output is correct |
29 |
Correct |
3 ms |
6744 KB |
Output is correct |
30 |
Correct |
3 ms |
6744 KB |
Output is correct |
31 |
Correct |
4 ms |
6748 KB |
Output is correct |
32 |
Correct |
4 ms |
7256 KB |
Output is correct |
33 |
Correct |
4 ms |
7256 KB |
Output is correct |
34 |
Correct |
4 ms |
7256 KB |
Output is correct |
35 |
Correct |
4 ms |
7256 KB |
Output is correct |
36 |
Correct |
4 ms |
7260 KB |
Output is correct |
37 |
Correct |
4 ms |
7256 KB |
Output is correct |
38 |
Correct |
3 ms |
6744 KB |
Output is correct |
39 |
Correct |
2 ms |
6748 KB |
Output is correct |
40 |
Correct |
4 ms |
7000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2648 KB |
Output is correct |
11 |
Correct |
1 ms |
2904 KB |
Output is correct |
12 |
Correct |
1 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
6488 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6748 KB |
Output is correct |
16 |
Correct |
6 ms |
7000 KB |
Output is correct |
17 |
Correct |
5 ms |
7004 KB |
Output is correct |
18 |
Correct |
4 ms |
7256 KB |
Output is correct |
19 |
Correct |
5 ms |
7000 KB |
Output is correct |
20 |
Correct |
5 ms |
7000 KB |
Output is correct |
21 |
Correct |
4 ms |
7000 KB |
Output is correct |
22 |
Correct |
4 ms |
6744 KB |
Output is correct |
23 |
Correct |
4 ms |
6844 KB |
Output is correct |
24 |
Correct |
5 ms |
6744 KB |
Output is correct |
25 |
Correct |
4 ms |
6748 KB |
Output is correct |
26 |
Correct |
4 ms |
6744 KB |
Output is correct |
27 |
Correct |
4 ms |
7000 KB |
Output is correct |
28 |
Correct |
3 ms |
4696 KB |
Output is correct |
29 |
Correct |
2 ms |
6744 KB |
Output is correct |
30 |
Correct |
3 ms |
6744 KB |
Output is correct |
31 |
Correct |
3 ms |
6744 KB |
Output is correct |
32 |
Correct |
4 ms |
6744 KB |
Output is correct |
33 |
Correct |
4 ms |
6744 KB |
Output is correct |
34 |
Correct |
4 ms |
7000 KB |
Output is correct |
35 |
Correct |
3 ms |
6744 KB |
Output is correct |
36 |
Correct |
3 ms |
6744 KB |
Output is correct |
37 |
Correct |
3 ms |
6744 KB |
Output is correct |
38 |
Correct |
4 ms |
6748 KB |
Output is correct |
39 |
Correct |
4 ms |
7256 KB |
Output is correct |
40 |
Correct |
4 ms |
7256 KB |
Output is correct |
41 |
Correct |
4 ms |
7256 KB |
Output is correct |
42 |
Correct |
4 ms |
7256 KB |
Output is correct |
43 |
Correct |
4 ms |
7260 KB |
Output is correct |
44 |
Correct |
4 ms |
7256 KB |
Output is correct |
45 |
Correct |
3 ms |
6744 KB |
Output is correct |
46 |
Correct |
2 ms |
6748 KB |
Output is correct |
47 |
Correct |
4 ms |
7000 KB |
Output is correct |
48 |
Correct |
274 ms |
32364 KB |
Output is correct |
49 |
Correct |
309 ms |
32768 KB |
Output is correct |
50 |
Correct |
332 ms |
32836 KB |
Output is correct |
51 |
Correct |
318 ms |
32972 KB |
Output is correct |
52 |
Correct |
303 ms |
32848 KB |
Output is correct |
53 |
Correct |
306 ms |
32856 KB |
Output is correct |
54 |
Correct |
321 ms |
32968 KB |
Output is correct |
55 |
Correct |
193 ms |
31980 KB |
Output is correct |
56 |
Correct |
256 ms |
32368 KB |
Output is correct |
57 |
Correct |
259 ms |
32432 KB |
Output is correct |
58 |
Correct |
256 ms |
32188 KB |
Output is correct |
59 |
Correct |
269 ms |
32336 KB |
Output is correct |
60 |
Correct |
252 ms |
32380 KB |
Output is correct |
61 |
Correct |
263 ms |
32396 KB |
Output is correct |
62 |
Correct |
2 ms |
2652 KB |
Output is correct |
63 |
Correct |
4 ms |
15704 KB |
Output is correct |
64 |
Correct |
128 ms |
18772 KB |
Output is correct |
65 |
Correct |
134 ms |
24176 KB |
Output is correct |
66 |
Correct |
217 ms |
32112 KB |
Output is correct |
67 |
Correct |
283 ms |
32112 KB |
Output is correct |
68 |
Correct |
287 ms |
32088 KB |
Output is correct |
69 |
Correct |
788 ms |
94580 KB |
Output is correct |
70 |
Correct |
787 ms |
94576 KB |
Output is correct |
71 |
Correct |
784 ms |
94712 KB |
Output is correct |
72 |
Correct |
1004 ms |
76428 KB |
Output is correct |
73 |
Correct |
790 ms |
94796 KB |
Output is correct |
74 |
Correct |
790 ms |
94544 KB |
Output is correct |
75 |
Correct |
215 ms |
32096 KB |
Output is correct |
76 |
Correct |
215 ms |
32280 KB |
Output is correct |
77 |
Correct |
221 ms |
32208 KB |
Output is correct |
78 |
Correct |
485 ms |
47768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2648 KB |
Output is correct |
11 |
Correct |
1 ms |
2904 KB |
Output is correct |
12 |
Correct |
1 ms |
2648 KB |
Output is correct |
13 |
Correct |
1 ms |
6488 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6748 KB |
Output is correct |
16 |
Correct |
1 ms |
6488 KB |
Output is correct |
17 |
Correct |
2 ms |
10840 KB |
Output is correct |
18 |
Correct |
2 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
15452 KB |
Output is correct |
20 |
Correct |
4 ms |
15452 KB |
Output is correct |
21 |
Correct |
3 ms |
15704 KB |
Output is correct |
22 |
Correct |
3 ms |
15448 KB |
Output is correct |
23 |
Correct |
3 ms |
15448 KB |
Output is correct |
24 |
Correct |
3 ms |
15448 KB |
Output is correct |
25 |
Correct |
3 ms |
15448 KB |
Output is correct |
26 |
Correct |
3 ms |
15448 KB |
Output is correct |
27 |
Correct |
6 ms |
7000 KB |
Output is correct |
28 |
Correct |
5 ms |
7004 KB |
Output is correct |
29 |
Correct |
4 ms |
7256 KB |
Output is correct |
30 |
Correct |
5 ms |
7000 KB |
Output is correct |
31 |
Correct |
5 ms |
7000 KB |
Output is correct |
32 |
Correct |
4 ms |
7000 KB |
Output is correct |
33 |
Correct |
4 ms |
6744 KB |
Output is correct |
34 |
Correct |
4 ms |
6844 KB |
Output is correct |
35 |
Correct |
5 ms |
6744 KB |
Output is correct |
36 |
Correct |
4 ms |
6748 KB |
Output is correct |
37 |
Correct |
4 ms |
6744 KB |
Output is correct |
38 |
Correct |
4 ms |
7000 KB |
Output is correct |
39 |
Correct |
3 ms |
4696 KB |
Output is correct |
40 |
Correct |
2 ms |
6744 KB |
Output is correct |
41 |
Correct |
3 ms |
6744 KB |
Output is correct |
42 |
Correct |
3 ms |
6744 KB |
Output is correct |
43 |
Correct |
4 ms |
6744 KB |
Output is correct |
44 |
Correct |
4 ms |
6744 KB |
Output is correct |
45 |
Correct |
4 ms |
7000 KB |
Output is correct |
46 |
Correct |
3 ms |
6744 KB |
Output is correct |
47 |
Correct |
3 ms |
6744 KB |
Output is correct |
48 |
Correct |
3 ms |
6744 KB |
Output is correct |
49 |
Correct |
4 ms |
6748 KB |
Output is correct |
50 |
Correct |
4 ms |
7256 KB |
Output is correct |
51 |
Correct |
4 ms |
7256 KB |
Output is correct |
52 |
Correct |
4 ms |
7256 KB |
Output is correct |
53 |
Correct |
4 ms |
7256 KB |
Output is correct |
54 |
Correct |
4 ms |
7260 KB |
Output is correct |
55 |
Correct |
4 ms |
7256 KB |
Output is correct |
56 |
Correct |
3 ms |
6744 KB |
Output is correct |
57 |
Correct |
2 ms |
6748 KB |
Output is correct |
58 |
Correct |
4 ms |
7000 KB |
Output is correct |
59 |
Correct |
274 ms |
32364 KB |
Output is correct |
60 |
Correct |
309 ms |
32768 KB |
Output is correct |
61 |
Correct |
332 ms |
32836 KB |
Output is correct |
62 |
Correct |
318 ms |
32972 KB |
Output is correct |
63 |
Correct |
303 ms |
32848 KB |
Output is correct |
64 |
Correct |
306 ms |
32856 KB |
Output is correct |
65 |
Correct |
321 ms |
32968 KB |
Output is correct |
66 |
Correct |
193 ms |
31980 KB |
Output is correct |
67 |
Correct |
256 ms |
32368 KB |
Output is correct |
68 |
Correct |
259 ms |
32432 KB |
Output is correct |
69 |
Correct |
256 ms |
32188 KB |
Output is correct |
70 |
Correct |
269 ms |
32336 KB |
Output is correct |
71 |
Correct |
252 ms |
32380 KB |
Output is correct |
72 |
Correct |
263 ms |
32396 KB |
Output is correct |
73 |
Correct |
2 ms |
2652 KB |
Output is correct |
74 |
Correct |
4 ms |
15704 KB |
Output is correct |
75 |
Correct |
128 ms |
18772 KB |
Output is correct |
76 |
Correct |
134 ms |
24176 KB |
Output is correct |
77 |
Correct |
217 ms |
32112 KB |
Output is correct |
78 |
Correct |
283 ms |
32112 KB |
Output is correct |
79 |
Correct |
287 ms |
32088 KB |
Output is correct |
80 |
Correct |
788 ms |
94580 KB |
Output is correct |
81 |
Correct |
787 ms |
94576 KB |
Output is correct |
82 |
Correct |
784 ms |
94712 KB |
Output is correct |
83 |
Correct |
1004 ms |
76428 KB |
Output is correct |
84 |
Correct |
790 ms |
94796 KB |
Output is correct |
85 |
Correct |
790 ms |
94544 KB |
Output is correct |
86 |
Correct |
215 ms |
32096 KB |
Output is correct |
87 |
Correct |
215 ms |
32280 KB |
Output is correct |
88 |
Correct |
221 ms |
32208 KB |
Output is correct |
89 |
Correct |
485 ms |
47768 KB |
Output is correct |
90 |
Correct |
297 ms |
34488 KB |
Output is correct |
91 |
Correct |
543 ms |
67816 KB |
Output is correct |
92 |
Correct |
626 ms |
67408 KB |
Output is correct |
93 |
Correct |
531 ms |
67752 KB |
Output is correct |
94 |
Correct |
549 ms |
67612 KB |
Output is correct |
95 |
Correct |
535 ms |
67784 KB |
Output is correct |
96 |
Correct |
532 ms |
67912 KB |
Output is correct |
97 |
Correct |
216 ms |
35256 KB |
Output is correct |
98 |
Correct |
472 ms |
67020 KB |
Output is correct |
99 |
Correct |
478 ms |
67916 KB |
Output is correct |
100 |
Correct |
473 ms |
67412 KB |
Output is correct |
101 |
Correct |
489 ms |
66992 KB |
Output is correct |
102 |
Correct |
467 ms |
66848 KB |
Output is correct |
103 |
Correct |
486 ms |
67396 KB |
Output is correct |
104 |
Correct |
327 ms |
51792 KB |
Output is correct |
105 |
Correct |
380 ms |
61776 KB |
Output is correct |
106 |
Correct |
617 ms |
75204 KB |
Output is correct |
107 |
Correct |
524 ms |
74580 KB |
Output is correct |
108 |
Correct |
560 ms |
74740 KB |
Output is correct |
109 |
Correct |
532 ms |
74576 KB |
Output is correct |
110 |
Correct |
532 ms |
74808 KB |
Output is correct |
111 |
Correct |
1214 ms |
129800 KB |
Output is correct |
112 |
Correct |
1221 ms |
129656 KB |
Output is correct |
113 |
Correct |
1481 ms |
130528 KB |
Output is correct |
114 |
Correct |
1774 ms |
94132 KB |
Output is correct |
115 |
Correct |
1420 ms |
130012 KB |
Output is correct |
116 |
Correct |
1235 ms |
130632 KB |
Output is correct |
117 |
Correct |
472 ms |
70884 KB |
Output is correct |
118 |
Correct |
511 ms |
71096 KB |
Output is correct |
119 |
Correct |
462 ms |
69072 KB |
Output is correct |
120 |
Correct |
554 ms |
71368 KB |
Output is correct |
121 |
Correct |
496 ms |
72208 KB |
Output is correct |
122 |
Correct |
812 ms |
76868 KB |
Output is correct |
123 |
Correct |
1830 ms |
94156 KB |
Output is correct |
124 |
Correct |
1578 ms |
87224 KB |
Output is correct |
125 |
Correct |
1443 ms |
84288 KB |
Output is correct |