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;
typedef long long ll;
const ll N = 2e5;
pair<ll,ll> lr[N];
ll v[N];
ll n,k,cnt = 0;
ll get(ll nr){
ll l = 0,r = cnt - 1;
while(l != r){
ll mij = (l + r + 1)/2;
if(lr[mij].second - lr[mij].first <= nr){
l = mij;
}else{
r = mij - 1;
}
}
return l;
}
int main(){
cin>>n>>k;
for(ll i = 0;i < n;i++){
cin>>v[i];
}
ll cur = 0,l = 0,r = 0;
lr[cnt++] = {0,0};
for(ll i = 0;i < k;i++){
ll x;
cin>>x;
cur+=x;
r = max(r,cur);
l = min(l,cur);
if(lr[cnt - 1] == pair<ll,ll>{l,r})continue;
lr[cnt++] = {l,r};
}
for(ll i = 0;i < n;i++){
ll ans = 0;
///add back
if(i == 0)ans+=abs(l);
else{
ll length = v[i] - v[i - 1];
ll id = get(length);
if(id == cnt - 1 || lr[id].first == lr[id + 1].first){
ans+=-lr[id].first;
}else{
ans+=length - lr[id].second;
}
}
if(i == n - 1)ans+=abs(r);
else{
ll length = v[i + 1] - v[i];
ll id = get(length);
if(id == cnt - 1 || lr[id].second == lr[id + 1].second){
ans+=lr[id].second;
}else{
ans+=length + lr[id].first;
}
}
cout<<ans<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |