#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
ll n,q;
cin>>n>>q;
vector<ll> vec(n);
for(int i=0;i<n;i++) cin>>vec[i];
vector<ll> wind(q);
for(int i=0;i<q;i++) cin>>wind[i];
for(int i=1;i<q;i++) wind[i]+=wind[i-1];
vector<ll> newind;
bool sign=(wind[0]>0);
ll curmax=wind[0];
for(int i=1;i<q;i++){
if(sign==1&&wind[i]>0){
curmax=max(curmax,wind[i]);
}
else if(sign==0&&wind[i]<0){
curmax=min(curmax,wind[i]);
}
else{
newind.push_back(curmax);
sign=(!sign);
curmax=wind[i];
}
}
if(curmax!=0) newind.push_back(curmax);
ll maxpos=0,maxneg=0,tmp=newind.size();
vector<pair<ll,ll>> fin;
for(int i=0;i<tmp;i++){
if(newind[i]<0){
maxneg=min(maxneg,newind[i]);
}
else{
if(newind[i]>maxpos){
fin.push_back(make_pair(newind[i],maxneg));
maxpos=newind[i];
}
}
}
ll len=fin.size(),curr,curl=vec[0]+maxneg;
bool flag=1;
for(auto x:wind) if(x>0) flag=0;
if(flag){
for(int i=0;i<n;i++){
cout<<vec[i]-curl<<"\n";
if(i!=n-1) curl=max(vec[i],vec[i+1]+maxneg);
}
return 0;
}
for(int i=0;i<n-1;i++){
ll dist=vec[i+1]-vec[i];
curl=max(curl,vec[i]+maxneg);
if(fin[0].first>=dist+fin[0].second){
cout<<dist+fin[0].second+vec[i]-curl<<"\n";
curl=dist+fin[0].second+vec[i];
continue;
}
ll l=0,r=len-1,ans=0;
while(l<r){
ll mid=(l+r)>>1;
if(min(fin[mid].first,dist+fin[mid].second)>min(fin[mid+1].first,dist+fin[mid+1].second)){
r=mid;
ans=max(ans,min(fin[mid].first,dist+fin[mid].second));
}
else if(min(fin[mid].first,dist+fin[mid].second)==min(fin[mid+1].first,dist+fin[mid+1].second)){
l=mid,r=mid;
ans=max(ans,min(fin[mid].first,dist+fin[mid].second));
}
else{
l=mid+1;
ans=max(ans,min(fin[mid+1].first,dist+fin[mid+1].second));
}
//cout<<l<<" "<<r<<" "<<ans<<"\n";
}
cout<<ans+vec[i]-curl<<"\n";
//cout<<ans+vec[i]<<" "<<curl<<"\n";
curl=ans+vec[i];
}
cout<<vec[n-1]+maxpos-max(curl,vec[n-1]+maxneg);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:45:23: warning: unused variable 'curr' [-Wunused-variable]
45 | ll len=fin.size(),curr,curl=vec[0]+maxneg;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
