#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, q;
cin >> n >> q;
vector<int> a(n + 2);
a[0] = -1e18;
a[n + 1] = 1e18;
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<int> shift(q + 1), mx(q + 2), mn(q + 2);
int sum = 0;
for (int i = 1; i <= q; ++i) {
cin >> shift[i];
sum += shift[i];
mn[i] = min(mn[i - 1], sum);
mx[i] = max(mx[i - 1], sum);
}
for (int i = 1; i <= n; ++i)
{
int res;
int l = 0, r = q;
while (l <= r) {
int m = (l + r) / 2;
if (a[i] + mx[m] <= a[i + 1] + mn[m]) {
res = m;
l = m + 1;
} else {
r = m - 1;
}
}
int right = a[i] + mx[res];
if (res != q && shift[res + 1] > 0)
right = a[i + 1] + mn[res];
l = 0, r = q;
res = -1;
while (l <= r) {
int m = (l + r) / 2;
if (a[i] + mn[m] >= a[i - 1] + mx[m]) {
res = m;
l = m + 1;
} else {
r = m - 1;
}
}
int left = a[i] + mn[res];
if (res != q && shift[res + 1] < 0)
left = a[i - 1] + mx[res];
cout << right - left << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |