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;
#define int long long
signed main() {
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];
int mn = 0, mx = 0;
int cur = 0;
int x;
map<int, int> mp;
mp[0] = 0;
for (int i = 1; i <= q; i++) {
cin >> x;
cur += x;
if (cur < mn) {
mp[cur] = i;
mn = cur;
}
if (cur > mx) {
mp[cur] = i;
mx = cur;
}
}
for (int i = 1; i <= n; i++) {
int left = a[i], right = a[i];
{
int l = a[i - 1], r = a[i];
while (r - l > 1) {
int mid = (l + r) / 2;
int x = mid - a[i];
int y = mid - a[i - 1];
auto it1 = mp.upper_bound(x);
if (it1 == mp.begin()) {
l = mid;
continue;
}
--it1;
auto it2 = mp.lower_bound(y);
if (it2 == mp.end()) {
r = mid;
continue;
}
if ((it1 -> second) < (it2 -> second))
r = mid;
else
l = mid;
}
auto it1 = mp.upper_bound(r - 1 - a[i]);
auto it2 = mp.lower_bound(r - a[i - 1]);
if ((it1 != mp.begin()) && ((it2 == mp.end()) ||((--it1) -> second < it2 -> second)))
r--;
left = r;
}
{
int l = a[i], r = a[i + 1];
while (r - l > 1) {
int mid = (l + r) / 2;
int x = mid - a[i];
int y = mid - a[i + 1];
auto it1 = mp.lower_bound(x);
if (it1 == mp.end()) {
r = mid;
continue;
}
auto it2 = mp.upper_bound(y);
if (it2 == mp.begin()) {
l = mid;
continue;
}
--it2;
if ((it1 -> second) < (it2 -> second))
l = mid;
else
r = mid;
}
auto it1 = mp.lower_bound(l + 1 - a[i]);
auto it2 = mp.upper_bound(l - a[i + 1]);
if ((it1 != mp.end()) && ((it2 == mp.begin() || (it1 -> second < (--it2) -> second))))
l++;
right = l;
}
cout << right - left << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |