Submission #799336

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

candies

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 2e5 ;
ll n, ans, num, a[N + 1], pref[N + 3] ;
set<pair<ll, ll>> s1, s2 ;
set<pair<ll, pair<ll, ll>>> s ;
ll get_sum(ll l, ll r)
{
    if(!l || r > n)return -1e18 ;
    ll num = 1 ;
    if(l % 2 == 0)num = -1 ;
    return (pref[r] - pref[l - 1]) * num ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(ll i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        s1.insert({i, i}) ;
        s2.insert({-i, -i}) ;
        pref[i] = pref[i - 1] ;
        if(i % 2)pref[i] += a[i] ;
        else pref[i] -= a[i] ;
        s.insert({a[i], {i, i}}) ;
    }
    pref[n + 1] = pref[n] ;
    for(ll i = 1 ; i <= (n + 1) / 2 ; i++)
    {
        ll num = (*s.rbegin()).fi, l = (*s.rbegin()).se.fi, r = (*s.rbegin()).se.se ;
        pair<ll, ll> pz1 = {l, r + 1}, pz2 = {-r, -l - 1} ;
        s.erase(*s.rbegin()) ;
        s1.erase({l, r}) ;
        s2.erase({-r, -l}) ;
        if(s1.lower_bound({l, r}) != s1.end())
            pz1 = *s1.lower_bound({l, r}) ;
        if(s2.lower_bound({-r, -l}) != s2.end())
            pz2 = *s2.lower_bound({-r, -l}) ;
        if(pz1.fi != l)s1.erase(pz1) ;
        if(-pz2.fi != r)s1.erase({-pz2.se, -pz2.fi}) ;
        if(-pz2.fi != r)s2.erase(pz2) ;
        if(pz1.se != r)s2.erase({-pz1.se, -pz1.fi}) ;
        if(pz1.fi != l)s.erase({get_sum(pz1.fi, pz1.se), {pz1.fi, pz1.se}}) ;
        if(-pz2.fi != r)s.erase({get_sum(-pz2.se, -pz2.fi), {-pz2.se, -pz2.fi}}) ;
        l = -pz2.se ;
        r = pz1.se ;
        s1.insert({l, r}) ;
        s2.insert({-r, -l}) ;
        s.insert({get_sum(l, r), {l, r}}) ;
        ans += num ;
        cout << ans << '\n' ;
    }
    return 0 ;
}

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