#include <bits/stdc++.h>
using namespace std;
long long n,q,a[200005],pt,lmax,rmax,mv,now,ans[200005],pos;
pair <long long,long long> gap[200005];
int main(){
cin >> n >> q;
for (int i=1;i<=n;i++){
cin >> a[i];
}
for (int i=2;i<=n;i++){
gap[i-1]=make_pair(a[i]-a[i-1],i);
}
sort(gap+1,gap+n);
for (int i=1;i<=q;i++){
cin >> mv;
now+=mv;
if (now < lmax){
lmax=now;
while (pt+1 < n && gap[pt+1].first <= -lmax+rmax){
pt++; pos=gap[pt].second;
ans[pos-1]+=rmax;
ans[pos]+=a[pos]-a[pos-1]-rmax;
}
}
else
if (now > rmax){
rmax=now;
while (pt+1 < n && gap[pt+1].first <= -lmax+rmax){
pt++; pos=gap[pt].second;
ans[pos]+=-lmax;
ans[pos-1]+=a[pos]-a[pos-1]-(-lmax);
}
}
}
for (int i=pt+1;i<n;i++){
pos=gap[i].second;
ans[pos-1]+=rmax;
ans[pos]+=-lmax;
}
ans[1]+=-lmax;
ans[n]+=rmax;
for (int i=1;i<=n;i++){
cout << ans[i] << "\n";
}
return 0;
}
//pre_neg[i] store i to i+1 from right
//pre_pos[i] store i to i+1 from left
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
4 ms |
364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
364 KB |
Output is correct |
| 6 |
Correct |
4 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Correct |
3 ms |
364 KB |
Output is correct |
| 10 |
Correct |
2 ms |
364 KB |
Output is correct |
| 11 |
Correct |
2 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
3 ms |
364 KB |
Output is correct |
| 17 |
Correct |
4 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
4 ms |
364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
364 KB |
Output is correct |
| 6 |
Correct |
4 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Correct |
3 ms |
364 KB |
Output is correct |
| 10 |
Correct |
2 ms |
364 KB |
Output is correct |
| 11 |
Correct |
2 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
3 ms |
364 KB |
Output is correct |
| 17 |
Correct |
4 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
105 ms |
492 KB |
Output is correct |
| 21 |
Correct |
96 ms |
492 KB |
Output is correct |
| 22 |
Correct |
79 ms |
364 KB |
Output is correct |
| 23 |
Correct |
82 ms |
364 KB |
Output is correct |
| 24 |
Correct |
96 ms |
1132 KB |
Output is correct |
| 25 |
Correct |
229 ms |
8172 KB |
Output is correct |
| 26 |
Correct |
221 ms |
8140 KB |
Output is correct |
| 27 |
Correct |
218 ms |
8044 KB |
Output is correct |
| 28 |
Correct |
247 ms |
7916 KB |
Output is correct |
| 29 |
Correct |
215 ms |
7820 KB |
Output is correct |
| 30 |
Correct |
228 ms |
7404 KB |
Output is correct |
| 31 |
Correct |
188 ms |
7020 KB |
Output is correct |
| 32 |
Correct |
198 ms |
7020 KB |
Output is correct |
| 33 |
Correct |
24 ms |
1132 KB |
Output is correct |
| 34 |
Correct |
249 ms |
8300 KB |
Output is correct |
| 35 |
Correct |
238 ms |
8044 KB |
Output is correct |
| 36 |
Correct |
269 ms |
8244 KB |
Output is correct |
| 37 |
Correct |
219 ms |
8044 KB |
Output is correct |
| 38 |
Correct |
221 ms |
7996 KB |
Output is correct |
| 39 |
Correct |
274 ms |
8096 KB |
Output is correct |
| 40 |
Correct |
236 ms |
8044 KB |
Output is correct |
| 41 |
Correct |
120 ms |
544 KB |
Output is correct |
| 42 |
Correct |
187 ms |
7020 KB |
Output is correct |
| 43 |
Correct |
257 ms |
8172 KB |
Output is correct |
| 44 |
Correct |
110 ms |
388 KB |
Output is correct |
| 45 |
Correct |
211 ms |
8044 KB |
Output is correct |
| 46 |
Correct |
254 ms |
8300 KB |
Output is correct |
| 47 |
Correct |
270 ms |
8252 KB |
Output is correct |
| 48 |
Correct |
261 ms |
8300 KB |
Output is correct |
