Submission #1088101

#TimeUsernameProblemLanguageResultExecution timeMemory
1088101DobromirAngelovCandies (JOI18_candies)C++14
100 / 100
354 ms30464 KiB
#include<bits/stdc++.h> #define endl '\n' #define fi first #define se second using namespace std; const int MAXN=2e5+5; const long long INF=1e18+5; int n; long long a[MAXN]; multiset<pair<long long,int> > vals; set<pair<int,long long> > inds; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { vals.insert({-a[i],i}); inds.insert({i,-a[i]}); } vals.insert({INF,0}); vals.insert({INF,n+1}); inds.insert({0,INF}); inds.insert({n+1,INF}); long long ans=0; for(int i=1;i<=(n+1)/2;i++) { auto cur=(*vals.begin()); ans-=cur.fi; cout<<ans<<endl; auto it=inds.lower_bound({cur.se,-INF}); it--; auto l=(*it); inds.erase(it++); auto m=(*it); inds.erase(it++); auto r=(*it); inds.erase(it); vals.erase({l.se, l.fi}); vals.erase({m.se, m.fi}); vals.erase({r.se, r.fi}); vals.insert({l.se+r.se-m.se, m.fi}); inds.insert({m.fi, l.se+r.se-m.se}); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...