Submission #709431

#	Time	Username	Problem	Language	Result	Execution time	Memory
709431		dooompy	Candies (JOI18_candies)	C++17	100 / 100	656 ms	28784 KiB

candies

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

multiset<pair<ll, ll>> vals, seen;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n; cin >> n;

    for (int i = 1; i <= n; i++) {
        ll a; cin >> a;
        vals.insert({-a, i});
        seen.insert({i, -a});
    }

    vals.insert({1e18, 0}); vals.insert({1e18, n + 1});
    seen.insert({0, 1e18}); seen.insert({n + 1, 1e18});

    ll ans = 0;

    for (int i = 1; i <= (n + 1) / 2; i++) {
        auto temp = vals.begin();

        ans += -(temp->first);
        cout << ans << "\n";

        auto seentemp = seen.lower_bound({temp->second, -1e9});
        seentemp--;

        pair<ll, ll> a = *seentemp;
        vals.erase({seentemp->second, seentemp->first});
        seen.erase(seentemp++);

        pair<ll, ll> b = *seentemp;
        vals.erase({seentemp->second, seentemp->first});
        seen.erase(seentemp++);

        pair<ll, ll> c = *seentemp;
        vals.erase({seentemp->second, seentemp->first});
        seen.erase(seentemp++);

        vals.insert({a.second + c.second - b.second, b.first});
        seen.insert({b.first, a.second + c.second - b.second});

    }
}

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