Submission #159324

#	Time	Username	Problem	Language	Result	Execution time	Memory
159324		fedoseevtimofey	Candies (JOI18_candies)	C++14	100 / 100	625 ms	32964 KiB

candies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Pt {
    int l, r; ll sum;
    bool operator <(const Pt &other) const {
        if (sum != other.sum) return sum > other.sum;
        return l < other.l;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <ll> pref(n + 1);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
    auto getSum = [&] (int l, int r) {
        return pref[r + 1] - pref[l];
    };
    set <Pt> q;
    for (int i = 0; i < n; ++i) q.insert({i, i, a[i]});
    vector <int> mL(n), mR(n);
    for (int i = 0; i < n; ++i) {
        mL[i] = i;
        mR[i] = i;
    }
    map <pair <int, int>, ll> sum;
    for (int i = 0; i < n; ++i) sum[{i, i}] = a[i];
    ll ans = 0;
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        auto cur = *q.begin();
        q.erase(q.begin());
        ans += cur.sum;
        cout << ans << '\n';
        int cl = cur.l, cr = cur.r;
        mR[cl] = mL[cr] = -1;
        ll cs = -cur.sum;
        int x = cur.r + 1;
        if (x < n) {
            int tl = x;
            int tr = mR[tl];
            if (tr != -1) {
                ll ts = sum[{tl, tr}];
                q.erase({tl, tr, ts});
                cr = tr;
                cs += ts;
                mR[tl] = mL[tr] = -1;
            }
        }
        x = cur.l - 1;
        if (x >= 0) {
            int tr = x;
            int tl = mL[tr];
            if (tl != -1) {
                ll ts = sum[{tl, tr}];
                q.erase({tl, tr, ts});
                cl = tl;
                cs += ts;
                mR[tl] = mL[tr] = -1;
            }
        }
        if (cl != cur.l && cr != cur.r) {
            mR[cl] = cr;
            mL[cr] = cl;
            sum[{cl, cr}] = cs;
            q.insert({cl, cr, cs});
        }
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:28:10: warning: variable 'getSum' set but not used [-Wunused-but-set-variable]
     auto getSum = [&] (int l, int r) {
          ^~~~~~

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