Submission #206906

#TimeUsernameProblemLanguageResultExecution timeMemory
206906achibasadzishviliCandies (JOI18_candies)C++17
100 / 100
933 ms27512 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back #define mp make_pair using namespace std; ll n,a[200005],ans; set<pair<ll,ll> >st; set<ll>ind; set<pair<ll,ll> >::iterator it; set<ll>::iterator itt; int main(){ ios::sync_with_stdio(false); cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; ind.insert(i); st.insert(mp(a[i] , i)); } a[0] = a[n + 1] = -99999999999999; ind.insert(0); ind.insert(n + 1); for(int i=1; i<=(n + 1) / 2; i++){ it = st.end(); it--; ll val = (*it).f , cur = (*it).s; st.erase(it); ans += val; ind.erase(ind.find(cur)); itt = ind.upper_bound(cur); a[cur] = -a[cur]; if(itt != ind.end()){ a[cur] += a[(*itt)]; st.erase(mp(a[(*itt)] , (*itt))); ind.erase(itt); } itt = ind.upper_bound(cur); if(itt != ind.begin()){ itt--; a[cur] += a[(*itt)]; st.erase(mp(a[(*itt)] , (*itt))); ind.erase(itt); } st.insert(mp(a[cur] , cur)); ind.insert(cur); cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...