This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long a[200005], w[200005];
long long mini[200005], maxi[200005];
main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
w[0] = 0;
mini[0] = 2e18;
maxi[0] = -2e18;
for (int i = 1; i <= q; ++i) {
cin >> w[i];
w[i] += w[i - 1];
mini[i] = min(mini[i - 1], w[i]);
maxi[i] = max(maxi[i - 1], w[i]);
}
for (int i = 1; i <= n; ++i) {
long long L, R;
if (i == 1) {
L = min(a[i], a[i] + mini[q]);
} else {
int l = 1, r = q;
while (l <= r) {
int mid = (l + r) / 2;
if (min(a[i], a[i] + mini[mid]) < max(a[i - 1], a[i - 1] + maxi[mid])) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l > q) {
L = min(a[i], a[i] + mini[q]);
} else {
L = max(a[i - 1], a[i - 1] + maxi[l]);
if (l > 1) {
L = min(L, min(a[i], a[i] + mini[l - 1]));
}
}
//cout << "i = " << i << " i_l = " << l << '\n';
}
if (i == n) {
R = max(a[i], a[i] + maxi[q]);
} else {
int l = 1, r = q;
while (l <= r) {
int mid = (l + r) / 2;
if (max(a[i], a[i] + maxi[mid]) > min(a[i + 1], a[i + 1] + mini[mid])) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l > q) {
R = max(a[i], a[i] + maxi[q]);
} else {
R = min(a[i + 1], a[i + 1] + mini[l]);
if (l > 1) {
R = max(R, max(a[i], a[i] + maxi[l - 1]));
}
}
//cout << "i = " << i << " i_r = " << l << '\n';
}
// cout <<"L = " << L<<" R = "<<R<<'\n';
cout << R - L << '\n';
}
}
Compilation message (stderr)
Main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
9 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |