Submission #1222874

#TimeUsernameProblemLanguageResultExecution timeMemory
1222874AlgorithmWarriorCandies (JOI18_candies)C++20
100 / 100
216 ms18020 KiB
#include <bits/stdc++.h> using namespace std; int const NMAX=200005; int lp[NMAX],rp[NMAX]; long long val[NMAX]; set<pair<long long,int>>upd; int n; void read(){ cin>>n; int i; lp[0]=0; rp[0]=1; lp[n+1]=n; rp[n+1]=n+1; for(i=1;i<=n;++i){ int value; cin>>value; lp[i]=i-1; rp[i]=i+1; val[i]=value; upd.insert({value,i}); } } void solve(){ long long sum=0; while(!upd.empty()){ auto [add,id]=*upd.rbegin(); sum+=add; cout<<sum<<'\n'; int id1=lp[id]; int id2=id; int id3=rp[id]; upd.erase({add,id}); if(id1>0) upd.erase({val[id1],id1}); if(id3<=n) upd.erase({val[id3],id3}); if(0<id1 && id3<=n){ rp[id1]=rp[id3]; lp[rp[id3]]=id1; val[id1]+=val[id3]-val[id2]; upd.insert({val[id1],id1}); } else if(0<id1){ rp[lp[id1]]=n+1; lp[n+1]=lp[id1]; } else if(id3<=n){ lp[rp[id3]]=0; rp[0]=rp[id3]; } else{ rp[0]=n+1; lp[n+1]=0; } } } int main() { read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...