#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
#ifndef ONLINE_JUDGE
#include "D:\cpp_codes\debugalgo.h"
#else
#define debug(x)
#endif
const ll inf = 1e18;
void solve()
{
int n,q;
cin>>n>>q;
vector<ll> a(n);
for(int i=0; i<n; i++)
{
cin>>a[i];
}
vector<ll> b(q);
for(int i=0; i<q; i++)
{
cin>>b[i];
if(i) b[i]+=b[i-1];
}
// debug(b);
vector<ll> mx(q,-inf),mn(q,inf);
mx[0] = max(0LL,b[0]);
mn[0] = min(0LL,b[0]);
for(int i=1; i<q; i++)
{
mx[i] = max({0LL,mx[i-1],b[i]});
mn[i] = min({0LL,mn[i-1],b[i]});
}
// debug(mn);
// debug(mx);
vector<pair<ll,pair<ll,ll>>> vright,vleft;
vright.push_back({mx[0],{mx[0],0LL}});
for(int i=1; i<q; i++)
{
vright.push_back({mx[i]-mn[i-1],{mx[i],mn[i-1]}});
}
// debug(vright);
vleft.push_back({-mn[0],{-mn[0],0LL}});
for(int i=1; i<q; i++)
{
vleft.push_back({mx[i-1]-mn[i],{-mn[i],mx[i-1]}});
}
// debug(vleft);
vector<ll> ans(n);
for(int i=0; i<n; i++)
{
ll left=-inf,right=-inf;
if(i==0)
{
left = -mn.back();
}
else
{
ll delta = a[i]-a[i-1];
auto itn = upper_bound(vleft.begin(),vleft.end(),make_pair(delta,make_pair(-1LL,-1LL)));
//intersecting
if(itn!=vleft.end())
{
left = max(left,delta - (*itn).second.second);
}
// no non-intersection
if(itn!=vleft.begin())
{
itn--;
left = max(left,(*itn).second.first);
}
}
if(i==n-1)
{
right = mx.back();
}
else
{
ll delta = a[i+1]-a[i];
auto it = upper_bound(vright.begin(),vright.end(),make_pair(delta,make_pair(-1LL,-1LL)));
//intersecting
if(it!=vright.end())
{
right = max(right, delta + (*it).second.second);
}
//non-intersecting
if(it!=vright.begin())
{
it--;
right = max(right, (*it).second.first);
}
}
ans[i] = left + right;
cout<<ans[i]<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("error.txt", "w", stderr);
// #endif
int tt = 1;
// cin >> tt;
while (tt--)
{
solve();
}
}
Compilation message
Main.cpp:9:10: fatal error: D:\cpp_codes\debugalgo.h: No such file or directory
9 | #include "D:\cpp_codes\debugalgo.h"
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
