#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
const long long inf = 1e18;
int n, q;
long long a[maxn + 1], v[maxn + 1], mx[maxn + 1], mn[maxn + 1], ans[maxn + 1];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
long long sum = 0;
for (int i = 1; i <= q; ++i){
cin >> v[i];
sum += v[i];
mx[i] = max(mx[i - 1], sum);
mn[i] = min(mn[i - 1], sum);
}
for (int i = 1; i <= n; ++i){
int lo = 1, hi = q;
long long res = 0;
while (lo <= hi){
int m = (lo + hi) >> 1;
long long lb = a[i] + mn[m], rb = (i == 1) ? -inf : a[i - 1] + mx[m];
res = max(res, a[i] - max(lb, rb));
if (lb > rb) lo = m + 1;
else hi = m - 1;
}
ans[i] += res;
lo = 1, hi = q, res = 0;
while (lo <= hi){
int m = (lo + hi) >> 1;
long long rb = a[i] + mx[m], lb = (i == n) ? inf : a[i + 1] + mn[m];
res = max(res, min(lb, rb) - a[i]);
if (rb < lb) lo = m + 1;
else hi = m - 1;
}
ans[i] += res;
}
for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |