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;
int N, Q;
long long x[200005];
long long w[200005];
long long d[200005];
long long lft[200005], rht[200005];
long long ans[200005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
for(int i = 1; i <= N; i++){
cin >> x[i];
}
for(int i = 1; i <= Q; i++){
cin >> d[i];
d[i] += d[i-1];
}
for(int i = 1; i <= Q; i++){
if(d[i] < 0){
rht[i] = -d[i];
}
else{
lft[i] = d[i];
}
rht[i] = max(rht[i], rht[i-1]);
lft[i] = max(lft[i], lft[i-1]);
}
ans[1] = rht[Q];
ans[N] += lft[Q];
for(int i = 1; i < N; i++){
if(lft[Q] + rht[Q] > x[i + 1] - x[i]){
int l = 1, r = N, k = 0;
while(l <= r){
int mid = (l + r)/2;
if(lft[mid] + rht[mid] < x[i + 1] - x[i]){
l = mid + 1;
}
else{
r = mid - 1;
k = mid;
}
}
ans[i] += lft[k-1];
ans[i+1] += rht[k-1];
if(lft[k-1] != lft[k]){
ans[i] += x[i + 1] - x[i] - lft[k-1] - rht[k-1];
}
else{
ans[i+1] += x[i+1] - x[i] - lft[k-1] - rht[k-1];
}
}
else{
ans[i] += lft[Q];
ans[i+1] += rht[Q];
}
}
for(int i = 1; i <= N; i++){
cout << ans[i];
if(i != N){
cout << "\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |