Submission #565487

#	Time	Username	Problem	Language	Result	Execution time	Memory
565487		lohacho	Candies (JOI18_candies)	C++14	0 / 100	3 ms	724 KiB

candies

#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    set<vector<int>> st1, st2;
    for(int i = 0; i < n; ++i){
        st1.insert({i, a[i], 1});
        st2.insert({a[i], i, 1});
    }
    int cnt = 0, sum = 0;
    while(cnt < (n + 1) / 2){
        auto p2 = prev(st2.end());
        int nowi = (*p2)[1];
        cnt += (*p2)[2], sum += (*p2)[0];
        if((*p2)[2] > 0){
            cout << sum << '\n';
        }
        int dcnt = -(*p2)[2], dsum = -(*p2)[0];
        auto p1 = st1.lower_bound(vector<int>{nowi, -(int)1e18, -(int)1e18});
        if(p1 != st1.begin()){
            auto p1p = prev(p1);
            dsum += (*p1p)[1];
            dcnt += (*p1p)[2];
            st2.erase(st2.find(vector<int>{(*p1p)[1], (*p1p)[0], (*p1p)[2]}));
            st1.erase(p1p);
        }
        auto p1n = next(p1);
        if(p1n != st1.end()){
            dsum += (*p1n)[1];
            dcnt += (*p1n)[2];
            st2.erase(st2.find(vector<int>{(*p1n)[1], (*p1n)[0], (*p1n)[2]}));
            st1.erase(p1n);
        }
        st2.insert({dsum, nowi, dcnt});
        st1.insert({nowi, dsum, dcnt});
        st2.erase(p2);
        st1.erase(p1);
    }
    return 0;
}

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