#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin>>n>>q;
vector<int> x(n), p(q), is(q);
for(int i=0;i<n;i++) cin>>x[i];
for(int i=0;i<q;i++){
cin>>p[i];
is[i] = (p[i] > 0);
if(i) p[i] += p[i-1];
}
vector<int> mn(q, 0), mx(q, 0);
for(int i=0;i<q;i++){
if(i) mn[i] = mn[i-1], mx[i] = mx[i-1];
mn[i] = min(mn[i], p[i]);
mx[i] = max(mx[i], p[i]);
}
vector<int> res(n);
for(int i=1;i<n;i++){
int l = 0, r = q;
auto check = [&](int t){
return (x[i-1] + mx[t] <= x[i] + mn[t]);
};
while(l < r){
int m = (l + r) >> 1;
if(check(m)) l = m + 1;
else r = m;
}
if(l < q){
int p;
if(is[l]) p = x[i] + (l ? mn[l-1] : 0);
else p = x[i-1] + (l ? mx[l-1] : 0);
res[i-1] += (p - x[i-1]);
res[i] += (x[i] - p);
} else {
res[i-1] += mx[q-1], res[i] += abs(mn[q-1]);
}
}
//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
//~ cout<<"\n";
res[0] += abs(mn[q-1]), res[n-1] += mx[q-1];
//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
//~ cout<<"\n";
for(int i=0;i<n;i++) cout<<res[i]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
308 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
2 ms |
460 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
308 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
2 ms |
460 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
320 KB |
Output is correct |
| 20 |
Correct |
30 ms |
8672 KB |
Output is correct |
| 21 |
Correct |
29 ms |
8432 KB |
Output is correct |
| 22 |
Correct |
32 ms |
8300 KB |
Output is correct |
| 23 |
Correct |
25 ms |
8180 KB |
Output is correct |
| 24 |
Correct |
36 ms |
8720 KB |
Output is correct |
| 25 |
Correct |
100 ms |
14984 KB |
Output is correct |
| 26 |
Correct |
120 ms |
14852 KB |
Output is correct |
| 27 |
Correct |
99 ms |
14732 KB |
Output is correct |
| 28 |
Correct |
103 ms |
14684 KB |
Output is correct |
| 29 |
Correct |
110 ms |
14220 KB |
Output is correct |
| 30 |
Correct |
95 ms |
13696 KB |
Output is correct |
| 31 |
Correct |
67 ms |
13056 KB |
Output is correct |
| 32 |
Correct |
95 ms |
13248 KB |
Output is correct |
| 33 |
Correct |
15 ms |
1808 KB |
Output is correct |
| 34 |
Correct |
111 ms |
15372 KB |
Output is correct |
| 35 |
Correct |
114 ms |
14720 KB |
Output is correct |
| 36 |
Correct |
99 ms |
15108 KB |
Output is correct |
| 37 |
Correct |
107 ms |
14720 KB |
Output is correct |
| 38 |
Correct |
100 ms |
14600 KB |
Output is correct |
| 39 |
Correct |
94 ms |
14728 KB |
Output is correct |
| 40 |
Correct |
72 ms |
14724 KB |
Output is correct |
| 41 |
Correct |
33 ms |
9284 KB |
Output is correct |
| 42 |
Correct |
65 ms |
13188 KB |
Output is correct |
| 43 |
Correct |
81 ms |
16512 KB |
Output is correct |
| 44 |
Correct |
35 ms |
9188 KB |
Output is correct |
| 45 |
Correct |
73 ms |
14724 KB |
Output is correct |
| 46 |
Correct |
78 ms |
16708 KB |
Output is correct |
| 47 |
Correct |
82 ms |
16912 KB |
Output is correct |
| 48 |
Correct |
86 ms |
16892 KB |
Output is correct |
