Submission #798944

#	Time	Username	Problem	Language	Result	Execution time	Memory
798944		vjudge1	Candies (JOI18_candies)	C++17	100 / 100	513 ms	28804 KiB

candies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 10;
const ll INF = 1e16;

int n;
ll a[N];
ll pr[N];

ll seg_sum(int l, int r) {
    if(l <= 0 || r > n) return INF;
    return pr[r - 1] - pr[l - 1];
}
ll inv_sum(int l, int r) {
    if(l <= 0 || r > n) return -INF;
    return pr[r] - pr[l] + a[l];
}
ll func(int l, int r) {
    return inv_sum(l, r) - seg_sum(l, r);
}
set<pair<ll, int>> Afree;
set<pair<int, int>> segments;
set<pair<ll, pair<int, int>>> inv_choices;
ll cur_ans = 0;
void inv_seg(int l, int r) {
    segments.erase({l, r});
    inv_choices.erase({func(l, r), {l, r}});
    cur_ans += func(l, r);
    l--, r++;
    if(!segments.empty()) {
        auto rseg = segments.upper_bound({l, r}), lseg = rseg; lseg--;
        if(rseg != segments.begin()) {
            if(lseg->second == l) {
                l = lseg->first;
                inv_choices.erase({func(lseg->first, lseg->second), {lseg->first, lseg->second}});
                segments.erase(lseg);
            }
        }
        if(rseg != segments.end()) {
            if(rseg->first == r) {
                r = rseg->second;
                inv_choices.erase({func(rseg->first, rseg->second), {rseg->first, rseg->second}});
                segments.erase(rseg);
            }
        }
    }
    segments.insert({l, r});
    inv_choices.insert({func(l, r), {l, r}});
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> a[i];
    for(int i = 1; i <= n + 1; i++) 
        pr[i] = a[i] + (i - 2 >= 0 ? pr[i - 2] : 0);
    
    for(int i = 1; i <= n; i++) 
        segments.insert({i, i}),
        inv_choices.insert({func(i, i), {i, i}});
    
    for(int _ = 1; _ <= (n + 1) / 2; _++) {
        auto [l, r] = (--inv_choices.end())->second;
        // cout << l << ' ' << r << '\n';
        inv_seg(l, r);
        cout << cur_ans << '\n';
        // for(auto [l, r] : segments) {
        //     cout << '{' << l << ' ' << r << '}' << ' ';
        // }
        // cout << '\n';
    }
}

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