Submission #145727

#	Time	Username	Problem	Language	Result	Execution time	Memory
145727		osaaateiasavtnl	Candies (JOI18_candies)	C++14	100 / 100	795 ms	25848 KiB

candies

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int a[N], d[N];
bool used[N];
struct Comp {
    bool operator () (int i, int j) { return (d[i] > d[j]) || (d[i] == d[j] && i < j); };
};
set <int> s1; set <int, Comp> s2;
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        d[i] = a[i];
        s1.insert(i); s2.insert(i);
    }
    int ans = 0;
    for (int _ = 1; _ <= (n + 1) / 2; ++_) {
        int i = *s2.begin(); s2.erase(s2.begin()); s1.erase(i);
        ans += d[i]; cout << ans << '\n';
        d[i] = -d[i];
        auto r = s1.upper_bound(i);
        bool c = 1;
        if (r != s1.end()) {
            d[i] += d[*r];
            s2.erase(*r); s1.erase(r);
        }
        else c = 0;
        auto l = s1.upper_bound(i);
        if (l != s1.begin()) {
            --l;
            d[i] += d[*l];
            s2.erase(*l); s1.erase(l);
        }
        else c = 0;
        if (c) { s1.insert(i); s2.insert(i); }
        #ifdef HOME
        for (int e : s1) cout << e << ' ' << d[e] << '\n';
        #endif
    }
}

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