#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+1;
ll n,q,a[N],ans[N];
vector<ll>megu,aquaa,aqua;
vector<ll>cc;
vector<ll>dm;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
ll x;
cin >> x;
if(x == 0) continue;
if(!megu.size()) megu.push_back(x);
else{
ll ccc = megu.back();
megu.push_back(ccc+x);
}
}
ll curd = 0;
ll curam = 0;
for(auto it: megu){
if(it > 0){
if(it > curd){
aquaa.push_back(it);
curd = it;
}
}
else{
if(abs(it) > curam){
aquaa.push_back(it);
curam = abs(it);
}
}
}
for(int i = 0; i < aquaa.size()-1; i++){
if((aquaa[i] > 0 && aquaa[i+1] < 0) || (aquaa[i+1] > 0 && aquaa[i] < 0)) aqua.push_back(aquaa[i]);
}
if(aquaa.size()) aqua.push_back(aquaa.back());
for(int i = 0; i < aqua.size()-1; i++) dm.push_back(abs(aqua[i])+abs(aqua[i+1]));
sort(dm.begin(),dm.end());
//for(auto it: dm) cout << it << " ";
//cout << "\n";
for(int i = 1; i <= n-1; i++){
if(!aqua.size()) continue;
ll x = a[i+1]-a[i];
int p = upper_bound(dm.begin(),dm.end(),x)-dm.begin()-1;
if(p == dm.size()-1 && p != -1){
if(aqua[p] > 0){
ans[i] += aqua[p];
ans[i+1] += abs(aqua[p+1]);
}
else{
ans[i] += aqua[p+1];
ans[i+1] += abs(aqua[p]);
}
}
else if(p == -1){
if(aqua[0] > 0){
ans[i] += min(aqua[0],x);
x -= aqua[0];
if(x > 0) ans[i+1] += x;
}
else{
ans[i+1] += min(abs(aqua[0]),x);
x -= abs(aqua[0]);
if(x > 0) ans[i] += x;
}
}
else{
if(aqua[p] > 0){
ans[i] += aqua[p]+x-dm[p];
ans[i+1] += abs(aqua[p+1]);
}
else{
ans[i] += aqua[p+1];
ans[i+1] += abs(aqua[p])+x-dm[p];
}
}
}
ans[1] += curam;
ans[n] += curd;
for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |