Submission #967511

#	Time	Username	Problem	Language	Result	Execution time	Memory
967511		Tuanlinh123	Candies (JOI18_candies)	C++17	100 / 100	261 ms	21224 KiB

candies

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=200005;
ll a[maxn], pre[2][maxn];
set <pll> range, profit;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<=n; i++)
    {
        cin >> a[i];
        pre[i&1][i]=pre[i&1][i-1]+a[i];
        pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
    } 
    pre[0][n+1]=pre[0][n], pre[1][n+1]=pre[1][n];
    // calculate range sum, index l and r are chosen
    auto sum=[&](ll l, ll r)
    {
        assert((r-l)%2==0); l--, r++;
        return pre[r&1][r]-(l?pre[r&1][l-1]:0);
    };
    for (ll i=1; i<=n; i++) profit.insert({a[i], i});
    ll ans=0;
    for (ll i=1; i<=(n+1)/2; i++)
    {
        auto [x, p]=*prev(profit.end()); profit.erase(prev(profit.end())), ans+=x, cout << ans << "\n";
        auto ptr=range.lower_bound(mp(p, 0));
        ll l=p, r=p;
        if (ptr!=range.end() && (*ptr).fi==p+1)
            r=(*ptr).se+1, ptr=range.erase(ptr);
        if (ptr!=range.end() && (*ptr).fi==r+2)
            r=(*ptr).se, r<n?profit.erase({sum((*ptr).fi, (*ptr).se), (*ptr).fi-1}),0:0, ptr=range.erase(ptr);
        else if (r+1<=n) profit.erase({a[r+1], r+1});
        if (ptr!=range.begin() && (*prev(ptr)).se==l-2)
            l=(*prev(ptr)).fi, l>1?profit.erase({sum((*prev(ptr)).fi, (*prev(ptr)).se), l-1}),0:0, range.erase(prev(ptr));
        else if (l-1>=1) profit.erase({a[l-1], l-1});
        if (l>1 && r<n) profit.insert({sum(l, r), l-1});
        range.insert({l, r});
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:25:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   25 |         pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
      |             ~^~
candies.cpp:25:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   25 |         pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
      |                           ~^~

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