Submission #251643

#	Time	Username	Problem	Language	Result	Execution time	Memory
251643		dantoh000	Candies (JOI18_candies)	C++14	100 / 100	626 ms	27140 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> iii;
int n;
set<iii> VLR, LRV;
ll ans = 0;
int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        ll x;
        scanf("%lld",&x);
        VLR.insert({x,i,i});
        LRV.insert({i,i,x});
    }
    for (int i = 1; i <= (n+1)/2; i++){
        /*for (auto x : VLR){
            ll a,b,c;
            tie(a,b,c) = x;
            printf("<%lld %lld %lld>",a,b,c);
        }
        printf("<- VLR\n");
        for (auto x : LRV){
            ll a,b,c;
            tie(a,b,c) = x;
            printf("<%lld %lld %lld>",a,b,c);
        }
        printf("<- LRV\n");*/
        ll v,l,r;
        tie(v,l,r) = *(--VLR.end());
        //printf("taking %lld %lld %lld\n",l,r,v);
        ans += v;
        ll nv = -v, nl = l, nr = r;
        auto it = LRV.find({l,r,v});
        assert(it != LRV.end());
        bool bad = 0;
        if (it != LRV.begin()){
            auto itL = prev(it);
            ll vL, lL, rL;
            tie(lL, rL, vL) = *itL;
            nv += vL;
            VLR.erase({vL,lL,rL});
            LRV.erase(itL);
            nl = lL;
            it = LRV.find({l,r,v});
        }
        else bad = 1;
        if (next(it) != LRV.end()){
            auto itR = next(it);
            ll vR, lR, rR;
            tie(lR, rR, vR) = *itR;
            nv += vR;
            VLR.erase({vR,lR,rR});
            LRV.erase(itR);
            nr = rR;
            it = LRV.find({l,r,v});
        }
        else bad = 1;
        VLR.erase(--VLR.end());
        LRV.erase(it);
        //printf("adding %lld %lld %lld\n",nl,nr,nv);
        if (!bad){
            VLR.insert({nv,nl,nr});
            LRV.insert({nl,nr,nv});
        }
        printf("%lld\n",ans);
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
candies.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~

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