#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const double eps=1e-6;
int32_t main()
{
int n,q; cin >> n >> q;
vector<int> pos(n),d(n,1e18);
for(int i=0;i<n;++i) cin >> pos[i];
for(int i=0;i<n-1;++i) d[i]=abs(pos[i+1]-pos[i]);
vector<int> Q;
int tmp,tmp_now=0,POS_MAX=0,NEG_MIN=0;
for(int i=0;i<q;++i){
cin >> tmp;
tmp_now+=tmp;
if(tmp_now>=0 && tmp_now>POS_MAX){
if(!Q.empty() && Q.back()>=0 && tmp_now>Q.back()) Q.pop_back();
Q.emplace_back(tmp_now);
}
if(tmp_now<0 && tmp_now<NEG_MIN){
if(!Q.empty() && Q.back()<0 && tmp_now<Q.back()) Q.pop_back();
Q.emplace_back(tmp_now);
}
POS_MAX=max(POS_MAX,tmp_now);
NEG_MIN=min(NEG_MIN,tmp_now);
}
map<int,pair<int,int>> MAP;
MAP[0]={0,0};
int POS=0, NEG=0,TOTAL=0;
for(int i=0;i<Q.size();++i){
if(Q[i]>0)
POS=Q[i];
else
NEG=-Q[i];
TAL=NEG+POS;
MAP[TOTAL]={POS,NEG};
}
int pre=0,ans;
for(int i=0;i<n;++i){
if(i==0)
pre=-NEG_MIN;
if(i==n-1){
pre+=POS_MAX;
cout << pre << '\n';
break;
}
pair<int,int> now_pair=MAP.upper_bound(d[i])->second,pre_pair=prev(MAP.upper_bound(d[i]))->second;
if(now_pair.first==pre_pair.first){
ans=pre+pre_pair.first;
pre=d[i]-pre_pair.first;
}
else{
ans=pre+d[i]-pre_pair.second;
pre=pre_pair.second;
}
cout << ans << '\n';
}
return 0;
}
/*
4 3
-2 3 5 8
2
-4
7
10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
*/
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:37:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<Q.size();++i){
| ~^~~~~~~~~
Main.cpp:42:9: error: 'TAL' was not declared in this scope; did you mean 'TOTAL'?
42 | TAL=NEG+POS;
| ^~~
| TOTAL
