Submission #44342

#TimeUsernameProblemLanguageResultExecution timeMemory
44342zadrgaCandies (JOI18_candies)C++14
100 / 100
1029 ms39376 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1LL << 55) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 200111 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; ll arr[maxn]; set<pair<ll, int> > s; set<pair<int, ll> > ind; vector<ll> ans; int main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%lld", arr + i); s.insert(mp(-arr[i], i)); ind.insert(mp(i, -arr[i])); } // ne smemo izbrati robnih, ker se število ohrani ind.insert(mp(0, INF)); ind.insert(mp(n + 1, INF)); s.insert(mp(INF, 0)); s.insert(mp(INF, n + 1)); ll cur = 0; for(int k = 0; k < (n + 1) / 2; k++){ vector<pair<ll, int> > v; auto it = s.begin(); cur = cur + (-it -> fi); ans.pb(cur); auto it1 = ind.lower_bound(mp(it -> se, -INF)); it1--; auto it2 = ind.lower_bound(mp(it -> se, -INF)); it2++; v.pb(*it); v.pb(mp(it1 -> se, it1 -> fi)); v.pb(mp(it2 -> se, it2 -> fi)); int pos = it -> se; ll tren = it1 -> se + it2 -> se - it -> fi; for(auto i : v){ s.erase(mp(i.fi, i.se)); ind.erase(mp(i.se, i.fi)); } s.insert(mp(tren, pos)); ind.insert(mp(pos, tren)); } for(ll i : ans) printf("%lld\n", i); return 0; }

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
candies.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", arr + i);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...