Submission #251641

# Submission time Handle Problem Language Result Execution time Memory
251641 2020-07-22T05:49:12 Z dantoh000 Candies (JOI18_candies) C++14
0 / 100
3 ms 640 KB
#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){
            int a,b,c;
            tie(a,b,c) = x;
            printf("<%d %d %d>",a,b,c);
        }
        printf("<- VLR\n");
        for (auto x : LRV){
            int a,b,c;
            tie(a,b,c) = x;
            printf("<%d %d %d>",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());
        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});
        }
        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});
        }
        VLR.erase(--VLR.end());
        LRV.erase(it);
        //printf("adding %lld %lld %lld\n",nl,nr,nv);
        VLR.insert({nv,nl,nr});
        LRV.insert({nl,nr,nv});
        printf("%lld\n",ans);
    }
}

Compilation message

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);
         ~~~~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -