Submission #45074

#	Time	Username	Problem	Language	Result	Execution time	Memory
45074		RayaBurong25_1	Candies (JOI18_candies)	C++17	100 / 100	734 ms	86316 KiB

candies

#include <stdio.h>
#include <map>
#include <set>
long long A[200005];
std::map<int, long long> V;
std::set<std::pair<long long, int> > PQ;
int cnt[200005];
// bool operator<(std::pair<long long, int> a, std::pair<long long, int> b)
// {
//     return (a.first < b.first || (a.first == b.first && a.second < b.second));
// }
int main()
{
    int N;
    scanf("%d", &N);
    int i;
    for (i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
        V.insert({i, A[i]});
        PQ.insert({-A[i], i});
        cnt[i] = 1;
    }
    long long sum = 0, r, diff;
    std::map<int, long long>::iterator p, q;
    std::set<std::pair<long long, int> >::iterator it;
    int s, inc, sumcnt = 0;
    for (i = 1; i <= (N + 1)/2;)
    {
        // for (p = V.begin(); p != V.end(); p++)
            // printf("V %d %lld %d\n", p->first, p->second, cnt[p->first]);
        // for (it = PQ.begin(); it != PQ.end(); it++)
            // printf("PQ %lld %d %d\n", (*it).first, (*it).second, cnt[it->second]);
        r = -PQ.begin()->first;
        s = PQ.begin()->second;
        if (cnt[s] == 0)
            r -= 1e18;
        sum += r;
        sumcnt += cnt[s];
        inc = -cnt[s];
        diff = 0;
        PQ.erase(PQ.begin());
        p = V.find(s);
        if (p != V.begin())
        {
            p--;
            diff += p->second;
            inc += cnt[p->first];
            s = p->first;
            PQ.erase({-p->second, p->first});
            p = V.erase(p);
        }
        diff -= p->second;
        p = V.erase(p);
        if (p != V.end())
        {
            diff += p->second;
            inc += cnt[p->first];
            PQ.erase({-p->second, p->first});
            p = V.erase(p);
        }
        cnt[s] = inc;
        if (inc == 0)
        {
            V.insert({s, diff});
            PQ.insert({1e18 - diff, s});
        }
        else
        {
            V.insert({s, diff});
            PQ.insert({-diff, s});
        }
        // printf("sumcnt %d\n", sumcnt);
        if (sumcnt == i)
        {
            printf("%lld\n", sum);
            i++;
        }
    }
}

Compilation message (stderr)

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

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