Submission #686619

#TimeUsernameProblemLanguageResultExecution timeMemory
686619PacybwoahSnowball (JOI21_ho_t2)C++14
0 / 100
3 ms340 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...