Submission #776464

#	Time	Username	Problem	Language	Result	Execution time	Memory
776464		tvladm2009	Candies (JOI18_candies)	C++17	100 / 100	449 ms	29656 KiB

candies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
const int N = (int) 2e5 + 7;
const ll INF = (ll) 1e18;
int n, sol[N];

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen("input", "r", stdin);

  cin >> n;
  set<pair<int, int>> s, revs;
  for (int i = 1; i <= n; i++) {
    ll x;
    cin >> x;
    s.insert({-x, i});
    revs.insert({i, -x});
  }
  s.insert({INF, 0});
  revs.insert({0, INF});
  s.insert({INF, n + 1});
  revs.insert({n + 1, INF});
  sol[0] = 0;
  for (int i = 1; i <= (n + 1) / 2; i++) {
    pair<int, int> now = *s.begin();
    sol[i] = sol[i - 1] - now.first;

    auto it = revs.lower_bound({now.second, -INF});
    it--;
    pair<int, int> x = *it;
    s.erase(s.find({x.second, x.first}));
    revs.erase(it++);

    pair<int, int> y = *it;
    s.erase(s.find({y.second, y.first}));
    revs.erase(it++);

    pair<int, int> z = *it;
    s.erase(s.find({z.second, z.first}));
    revs.erase(it++);

    revs.insert({y.first, x.second + z.second - y.second});
    s.insert({x.second + z.second - y.second, y.first});
  }

  for (int i = 1; i <= (n + 1) / 2; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92