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;
const long long maxn = 2e5 + 12, mod = 1e9 + 7;
long long n, a[maxn], qer[maxn], ans[maxn], sum[maxn][2];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
int q;
cin >> n >> q;
for(int i = 0; i < n; i++)
cin >> a[i];
long long d = 0;
for(int i = 1; i <= q; i++){
long long b;
cin >> b;
qer[i] = b;
d += b;
sum[i][1] = max(-d, sum[i - 1][1]);
sum[i][0] = max(d, sum[i - 1][0]);
}
// for(int i = 1; i <= q; i++)
// cout << sum[i][0] << ' ' << sum[i][1] << endl;
for(int i = 0; i < n - 1; i++){
long long f = a[i];
long long s = a[i + 1];
long long l = 0, r = q + 1, mid;
while(r - l != 1){
mid = (l + r) / 2;
if(sum[mid][0] + sum[mid][1] <= s - f)
l = mid;
else
r = mid;
}
ans[i] += sum[l][0];
ans[i + 1] += sum[l][1];
if(qer[l + 1] >= 0)
ans[i] += s - f - sum[l][0] - sum[l][1];
else
ans[i + 1] += s - f - sum[l][0] - sum[l][1];
}
ans[0] += sum[q][1];
ans[n - 1] += sum[q][0];
for(int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |