Submission #829821

#	Time	Username	Problem	Language	Result	Execution time	Memory
829821		vjudge1	Candies (JOI18_candies)	C++17	0 / 100	2 ms	468 KiB

candies

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 200200;

ll pref[N], ans, n;

ll get(int l, int r) {
    return pref[r - (r == n - 1 ? (r^l)&1 : 0)] - (l > 1 ? pref[l - 2] : 0ll);
}

ll inv(int l, int r) {
    return l == r ? 0ll : get(l + 1, r - !((r^l)&1));
}

ll f(pair < int, int > seg) {
    auto &[l, r] = seg;
    return get(l, r) - inv(l, r);
}

set < pair < int, int > > segs;
set < pair < ll, pair < int, int > > > flips;

void flip(int l, int r) {
    auto it = segs.find({l, r}), l_seg = it, r_seg = it;
    flips.erase(flips.find({f(*it), *it}));
    if(it != segs.begin()) {
        -- l_seg;
        flips.erase(flips.find({f(*l_seg), *l_seg})); 
        l = l_seg -> first;
        segs.erase(l_seg);
    } 
    ++ r_seg;
    if(r_seg != segs.end()) {
        flips.erase(flips.find({f(*r_seg), *r_seg}));
        r = r_seg -> second;
        segs.erase(r_seg);
    }
    segs.erase(it);

    segs.insert({l, r});
    flips.insert({f({l, r}), {l, r}});
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; ++ i) {
        cin >> pref[i];
        pref[i] += (i > 1 ? pref[i - 2] : 0ll);
        flips.insert({f({i, i}), {i, i}});
        segs.insert({i, i});
    }

    for(int t = (n + 1) / 2; t --> 0;) {
        auto [l, r] = flips.rbegin()->second;
        //cout << l << ' ' << r << ' ' << flips.rbegin()->first << '\n';
        ans += flips.rbegin()->first;
        flip(l, r);
        /**
        for(auto &[val, t] : flips) {
            cout << val << ' ' << t.first << ' ' << t.second << '\n';
        }
        // */
        cout << ans << '\n';
    }   
}

Compilation message (stderr)

candies.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main() {
      | ^~~~

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