#ifndef LOCAL
#include "overtaking.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define cerr if(0)cerr
#endif
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pi;
const int N=1e3+5,N_=1<<21;
struct B {ll s,t;int i;}b[N][N];
ll ans[N][N];
bool operator<(B a,B b){return a.s!=b.s?a.s<b.s:a.t<b.t;}
ll xx[N_];
int n_,k;
pi st[N_*2];
pi qry(ll x){
int p=upper_bound(xx,xx+k,x)-xx-1;
p+=n_;
pi v{N,0};
while(p>0)v=min(v,st[p]),p>>=1;
return v;
}
void upd(ll l,ll r,pi x){
if(l<=r){
int ql=upper_bound(xx,xx+k,l)-xx-1;
int qr=upper_bound(xx,xx+k,r)-xx-1;
for(ql+=n_,qr+=n_;ql<=qr;ql>>=1,qr>>=1){
if(ql&1)st[ql]=min(st[ql],x),ql++;
if(~qr&1)st[qr]=min(st[qr],x),qr--;
}
}
}
ll l,x;
void init(int l_,int n,vector<ll>t,vi w,int x_,int m,vi s){
l=l_,x=x_;
for(int i=0;i<n;i++)b[0][i]={0,t[i],i};
n_=0;
for(int t=1;t<m;t++){
for(int i=0;i<n;i++){
auto[s_,t_,i_]=b[t-1][i];
b[t][i]={t_,t_+1ll*w[i_]*(s[t]-s[t-1]),i_};
}
sort(b[t],b[t]+n);
for(int i=1;i<n;i++)b[t][i].t=max(b[t][i].t,b[t][i-1].t);
for(int i=0;i<n;i++){
xx[n_++]=b[t][i].s-x*s[t-1]+1;
xx[n_++]=b[t][i].t-x*s[t];
}
}
xx[n_++]=-4e18;
sort(xx,xx+n_);
k=unique(xx,xx+n_)-xx;
n_=1;while(n_<k)n_<<=1;
for(int i=1;i<n_*2;i++)st[i]={N,0};
for(int t=m-1;t>=1;t--){
for(int i=0;i<n;i++){
pi p=qry(b[t][i].t-x*s[t]);p.second*=-1;
if(p==pi{N,0})ans[t][i]=b[t][i].t+x*(l-s[t]);
else ans[t][i]=ans[p.first][p.second];
}
for(int i=0;i<n;i++)upd(b[t][i].s-x*s[t-1]+1,b[t][i].t-x*s[t]-1,pi{t,-i});
}
}
ll arrival_time(ll t){
pi p=qry(t);p.second*=-1;
if(p==pi{N,0})return t+x*l;
return ans[p.first][p.second];
}
#ifdef LOCAL
int main(){
cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
int l,n,x,m,q;
cin>>l>>n>>x>>m>>q;
vector<ll> t(n);
vi w(n),s(m);
for(int i=0;i<n;i++)cin>>t[i];
for(int i=0;i<n;i++)cin>>w[i];
for(int i=0;i<m;i++)cin>>s[i];
init(l,n,t,w,x,m,s);
for(int h=1;h<=q;h++){
ll t;
cin>>t;
cout<<"query t="<<t<<" got "<<arrival_time(t)<<'\n';
}
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
10588 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
3 ms |
20828 KB |
Output is correct |
7 |
Correct |
4 ms |
31068 KB |
Output is correct |
8 |
Correct |
4 ms |
35420 KB |
Output is correct |
9 |
Correct |
5 ms |
35416 KB |
Output is correct |
10 |
Correct |
4 ms |
35420 KB |
Output is correct |
11 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 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 |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6500 KB |
Output is correct |
9 |
Correct |
2 ms |
6556 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6488 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10588 KB |
Output is correct |
5 |
Correct |
1 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
5 ms |
12892 KB |
Output is correct |
10 |
Correct |
6 ms |
12892 KB |
Output is correct |
11 |
Correct |
7 ms |
12892 KB |
Output is correct |
12 |
Correct |
5 ms |
12892 KB |
Output is correct |
13 |
Correct |
6 ms |
13148 KB |
Output is correct |
14 |
Correct |
5 ms |
12892 KB |
Output is correct |
15 |
Correct |
6 ms |
13148 KB |
Output is correct |
16 |
Correct |
5 ms |
12892 KB |
Output is correct |
17 |
Correct |
5 ms |
12888 KB |
Output is correct |
18 |
Correct |
5 ms |
12916 KB |
Output is correct |
19 |
Correct |
6 ms |
12892 KB |
Output is correct |
20 |
Correct |
5 ms |
12892 KB |
Output is correct |
21 |
Correct |
4 ms |
12892 KB |
Output is correct |
22 |
Correct |
4 ms |
12892 KB |
Output is correct |
23 |
Correct |
3 ms |
10588 KB |
Output is correct |
24 |
Correct |
5 ms |
12892 KB |
Output is correct |
25 |
Correct |
5 ms |
12924 KB |
Output is correct |
26 |
Correct |
5 ms |
12892 KB |
Output is correct |
27 |
Correct |
5 ms |
12892 KB |
Output is correct |
28 |
Correct |
4 ms |
12892 KB |
Output is correct |
29 |
Correct |
4 ms |
12892 KB |
Output is correct |
30 |
Correct |
4 ms |
13148 KB |
Output is correct |
31 |
Correct |
4 ms |
12904 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
5 ms |
12892 KB |
Output is correct |
34 |
Correct |
5 ms |
12892 KB |
Output is correct |
35 |
Correct |
5 ms |
12892 KB |
Output is correct |
36 |
Correct |
6 ms |
12920 KB |
Output is correct |
37 |
Correct |
5 ms |
12892 KB |
Output is correct |
38 |
Correct |
2 ms |
10588 KB |
Output is correct |
39 |
Correct |
2 ms |
10588 KB |
Output is correct |
40 |
Correct |
4 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10588 KB |
Output is correct |
5 |
Correct |
1 ms |
10588 KB |
Output is correct |
6 |
Correct |
2 ms |
10588 KB |
Output is correct |
7 |
Correct |
3 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
31068 KB |
Output is correct |
9 |
Correct |
4 ms |
35420 KB |
Output is correct |
10 |
Correct |
5 ms |
35416 KB |
Output is correct |
11 |
Correct |
4 ms |
35420 KB |
Output is correct |
12 |
Correct |
4 ms |
35420 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
5 ms |
12892 KB |
Output is correct |
17 |
Correct |
6 ms |
12892 KB |
Output is correct |
18 |
Correct |
7 ms |
12892 KB |
Output is correct |
19 |
Correct |
5 ms |
12892 KB |
Output is correct |
20 |
Correct |
6 ms |
13148 KB |
Output is correct |
21 |
Correct |
5 ms |
12892 KB |
Output is correct |
22 |
Correct |
6 ms |
13148 KB |
Output is correct |
23 |
Correct |
5 ms |
12892 KB |
Output is correct |
24 |
Correct |
5 ms |
12888 KB |
Output is correct |
25 |
Correct |
5 ms |
12916 KB |
Output is correct |
26 |
Correct |
6 ms |
12892 KB |
Output is correct |
27 |
Correct |
5 ms |
12892 KB |
Output is correct |
28 |
Correct |
4 ms |
12892 KB |
Output is correct |
29 |
Correct |
4 ms |
12892 KB |
Output is correct |
30 |
Correct |
3 ms |
10588 KB |
Output is correct |
31 |
Correct |
5 ms |
12892 KB |
Output is correct |
32 |
Correct |
5 ms |
12924 KB |
Output is correct |
33 |
Correct |
5 ms |
12892 KB |
Output is correct |
34 |
Correct |
5 ms |
12892 KB |
Output is correct |
35 |
Correct |
4 ms |
12892 KB |
Output is correct |
36 |
Correct |
4 ms |
12892 KB |
Output is correct |
37 |
Correct |
4 ms |
13148 KB |
Output is correct |
38 |
Correct |
4 ms |
12904 KB |
Output is correct |
39 |
Correct |
3 ms |
12892 KB |
Output is correct |
40 |
Correct |
5 ms |
12892 KB |
Output is correct |
41 |
Correct |
5 ms |
12892 KB |
Output is correct |
42 |
Correct |
5 ms |
12892 KB |
Output is correct |
43 |
Correct |
6 ms |
12920 KB |
Output is correct |
44 |
Correct |
5 ms |
12892 KB |
Output is correct |
45 |
Correct |
2 ms |
10588 KB |
Output is correct |
46 |
Correct |
2 ms |
10588 KB |
Output is correct |
47 |
Correct |
4 ms |
10588 KB |
Output is correct |
48 |
Correct |
805 ms |
81196 KB |
Output is correct |
49 |
Correct |
724 ms |
81236 KB |
Output is correct |
50 |
Correct |
759 ms |
81512 KB |
Output is correct |
51 |
Correct |
709 ms |
81232 KB |
Output is correct |
52 |
Correct |
729 ms |
81232 KB |
Output is correct |
53 |
Correct |
715 ms |
81236 KB |
Output is correct |
54 |
Correct |
724 ms |
81484 KB |
Output is correct |
55 |
Correct |
599 ms |
81184 KB |
Output is correct |
56 |
Correct |
623 ms |
81228 KB |
Output is correct |
57 |
Correct |
634 ms |
81220 KB |
Output is correct |
58 |
Correct |
657 ms |
81264 KB |
Output is correct |
59 |
Correct |
645 ms |
81236 KB |
Output is correct |
60 |
Correct |
647 ms |
81224 KB |
Output is correct |
61 |
Correct |
661 ms |
81244 KB |
Output is correct |
62 |
Correct |
6 ms |
35416 KB |
Output is correct |
63 |
Correct |
3 ms |
6748 KB |
Output is correct |
64 |
Correct |
358 ms |
60512 KB |
Output is correct |
65 |
Correct |
331 ms |
47696 KB |
Output is correct |
66 |
Correct |
281 ms |
50276 KB |
Output is correct |
67 |
Correct |
784 ms |
81236 KB |
Output is correct |
68 |
Correct |
795 ms |
81248 KB |
Output is correct |
69 |
Correct |
282 ms |
66864 KB |
Output is correct |
70 |
Correct |
508 ms |
81228 KB |
Output is correct |
71 |
Correct |
532 ms |
81240 KB |
Output is correct |
72 |
Correct |
569 ms |
81484 KB |
Output is correct |
73 |
Correct |
556 ms |
81264 KB |
Output is correct |
74 |
Correct |
532 ms |
81256 KB |
Output is correct |
75 |
Correct |
157 ms |
50516 KB |
Output is correct |
76 |
Correct |
158 ms |
50276 KB |
Output is correct |
77 |
Correct |
163 ms |
52564 KB |
Output is correct |
78 |
Correct |
379 ms |
58664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10588 KB |
Output is correct |
5 |
Correct |
1 ms |
10588 KB |
Output is correct |
6 |
Correct |
2 ms |
10588 KB |
Output is correct |
7 |
Correct |
3 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
31068 KB |
Output is correct |
9 |
Correct |
4 ms |
35420 KB |
Output is correct |
10 |
Correct |
5 ms |
35416 KB |
Output is correct |
11 |
Correct |
4 ms |
35420 KB |
Output is correct |
12 |
Correct |
4 ms |
35420 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6492 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6492 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6500 KB |
Output is correct |
21 |
Correct |
2 ms |
6556 KB |
Output is correct |
22 |
Correct |
2 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Correct |
2 ms |
6488 KB |
Output is correct |
27 |
Correct |
5 ms |
12892 KB |
Output is correct |
28 |
Correct |
6 ms |
12892 KB |
Output is correct |
29 |
Correct |
7 ms |
12892 KB |
Output is correct |
30 |
Correct |
5 ms |
12892 KB |
Output is correct |
31 |
Correct |
6 ms |
13148 KB |
Output is correct |
32 |
Correct |
5 ms |
12892 KB |
Output is correct |
33 |
Correct |
6 ms |
13148 KB |
Output is correct |
34 |
Correct |
5 ms |
12892 KB |
Output is correct |
35 |
Correct |
5 ms |
12888 KB |
Output is correct |
36 |
Correct |
5 ms |
12916 KB |
Output is correct |
37 |
Correct |
6 ms |
12892 KB |
Output is correct |
38 |
Correct |
5 ms |
12892 KB |
Output is correct |
39 |
Correct |
4 ms |
12892 KB |
Output is correct |
40 |
Correct |
4 ms |
12892 KB |
Output is correct |
41 |
Correct |
3 ms |
10588 KB |
Output is correct |
42 |
Correct |
5 ms |
12892 KB |
Output is correct |
43 |
Correct |
5 ms |
12924 KB |
Output is correct |
44 |
Correct |
5 ms |
12892 KB |
Output is correct |
45 |
Correct |
5 ms |
12892 KB |
Output is correct |
46 |
Correct |
4 ms |
12892 KB |
Output is correct |
47 |
Correct |
4 ms |
12892 KB |
Output is correct |
48 |
Correct |
4 ms |
13148 KB |
Output is correct |
49 |
Correct |
4 ms |
12904 KB |
Output is correct |
50 |
Correct |
3 ms |
12892 KB |
Output is correct |
51 |
Correct |
5 ms |
12892 KB |
Output is correct |
52 |
Correct |
5 ms |
12892 KB |
Output is correct |
53 |
Correct |
5 ms |
12892 KB |
Output is correct |
54 |
Correct |
6 ms |
12920 KB |
Output is correct |
55 |
Correct |
5 ms |
12892 KB |
Output is correct |
56 |
Correct |
2 ms |
10588 KB |
Output is correct |
57 |
Correct |
2 ms |
10588 KB |
Output is correct |
58 |
Correct |
4 ms |
10588 KB |
Output is correct |
59 |
Correct |
805 ms |
81196 KB |
Output is correct |
60 |
Correct |
724 ms |
81236 KB |
Output is correct |
61 |
Correct |
759 ms |
81512 KB |
Output is correct |
62 |
Correct |
709 ms |
81232 KB |
Output is correct |
63 |
Correct |
729 ms |
81232 KB |
Output is correct |
64 |
Correct |
715 ms |
81236 KB |
Output is correct |
65 |
Correct |
724 ms |
81484 KB |
Output is correct |
66 |
Correct |
599 ms |
81184 KB |
Output is correct |
67 |
Correct |
623 ms |
81228 KB |
Output is correct |
68 |
Correct |
634 ms |
81220 KB |
Output is correct |
69 |
Correct |
657 ms |
81264 KB |
Output is correct |
70 |
Correct |
645 ms |
81236 KB |
Output is correct |
71 |
Correct |
647 ms |
81224 KB |
Output is correct |
72 |
Correct |
661 ms |
81244 KB |
Output is correct |
73 |
Correct |
6 ms |
35416 KB |
Output is correct |
74 |
Correct |
3 ms |
6748 KB |
Output is correct |
75 |
Correct |
358 ms |
60512 KB |
Output is correct |
76 |
Correct |
331 ms |
47696 KB |
Output is correct |
77 |
Correct |
281 ms |
50276 KB |
Output is correct |
78 |
Correct |
784 ms |
81236 KB |
Output is correct |
79 |
Correct |
795 ms |
81248 KB |
Output is correct |
80 |
Correct |
282 ms |
66864 KB |
Output is correct |
81 |
Correct |
508 ms |
81228 KB |
Output is correct |
82 |
Correct |
532 ms |
81240 KB |
Output is correct |
83 |
Correct |
569 ms |
81484 KB |
Output is correct |
84 |
Correct |
556 ms |
81264 KB |
Output is correct |
85 |
Correct |
532 ms |
81256 KB |
Output is correct |
86 |
Correct |
157 ms |
50516 KB |
Output is correct |
87 |
Correct |
158 ms |
50276 KB |
Output is correct |
88 |
Correct |
163 ms |
52564 KB |
Output is correct |
89 |
Correct |
379 ms |
58664 KB |
Output is correct |
90 |
Correct |
839 ms |
83552 KB |
Output is correct |
91 |
Correct |
1056 ms |
106948 KB |
Output is correct |
92 |
Correct |
1112 ms |
106448 KB |
Output is correct |
93 |
Correct |
1050 ms |
106684 KB |
Output is correct |
94 |
Correct |
1066 ms |
106400 KB |
Output is correct |
95 |
Correct |
1045 ms |
106468 KB |
Output is correct |
96 |
Correct |
1034 ms |
106580 KB |
Output is correct |
97 |
Correct |
629 ms |
83560 KB |
Output is correct |
98 |
Correct |
968 ms |
106488 KB |
Output is correct |
99 |
Correct |
969 ms |
107012 KB |
Output is correct |
100 |
Correct |
990 ms |
106464 KB |
Output is correct |
101 |
Correct |
990 ms |
106444 KB |
Output is correct |
102 |
Correct |
986 ms |
106444 KB |
Output is correct |
103 |
Correct |
992 ms |
106700 KB |
Output is correct |
104 |
Correct |
681 ms |
84956 KB |
Output is correct |
105 |
Correct |
793 ms |
74488 KB |
Output is correct |
106 |
Correct |
571 ms |
82204 KB |
Output is correct |
107 |
Correct |
1150 ms |
110728 KB |
Output is correct |
108 |
Correct |
1205 ms |
111060 KB |
Output is correct |
109 |
Correct |
1186 ms |
110788 KB |
Output is correct |
110 |
Correct |
1264 ms |
110788 KB |
Output is correct |
111 |
Correct |
594 ms |
92460 KB |
Output is correct |
112 |
Correct |
821 ms |
106692 KB |
Output is correct |
113 |
Correct |
976 ms |
108040 KB |
Output is correct |
114 |
Correct |
1120 ms |
108748 KB |
Output is correct |
115 |
Correct |
933 ms |
107980 KB |
Output is correct |
116 |
Correct |
843 ms |
107764 KB |
Output is correct |
117 |
Correct |
408 ms |
77924 KB |
Output is correct |
118 |
Correct |
411 ms |
77904 KB |
Output is correct |
119 |
Correct |
406 ms |
77060 KB |
Output is correct |
120 |
Correct |
416 ms |
79964 KB |
Output is correct |
121 |
Correct |
419 ms |
78944 KB |
Output is correct |
122 |
Correct |
683 ms |
81436 KB |
Output is correct |
123 |
Correct |
1191 ms |
108760 KB |
Output is correct |
124 |
Correct |
1221 ms |
108900 KB |
Output is correct |
125 |
Correct |
1237 ms |
109140 KB |
Output is correct |