Submission #203818

#	Time	Username	Problem	Language	Result	Execution time	Memory
203818		ho94949	Candies (JOI18_candies)	C++17	100 / 100	340 ms	16504 KiB

candies

#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const int MAXN = 262144;
int N;
long long arr[MAXN];

int idx[2*MAXN];

void setv(int a, long long v)
{
    arr[a] = v;
    idx[a+MAXN] = a;
    a += MAXN;
    while((a=a/2))
    {
        if(arr[idx[2*a]] < arr[idx[2*a+1]])
            idx[a] = idx[2*a+1];
        else
            idx[a] = idx[2*a];
    }
}
int geti()
{
    return idx[1];
}

int main()
{
    int N; scanf("%d", &N);
    set<int> S;
    setv(0, -INF); S.insert(0);
    for(int i=1; i<=N; ++i)
    {
        long long t; scanf("%lld", &t);
        setv(i, t); S.insert(i);
    }
    setv(N+1, -INF); S.insert(N+1);


    auto query = [&]()
    {
        int idx = geti(); long long retv = arr[idx];


        auto it = S.find(idx);
        auto it2 = it; --it2; int pidx = *it2;
        auto it3 = it; ++it3; int nidx = *it3;

        S.erase(it2); S.erase(it3);
        long long newval = arr[pidx]+arr[nidx] - arr[idx];
        setv(pidx, -INF);
        setv(nidx, -INF);
        setv(idx, newval);

        return retv;
    };

    long long ans = 0;
    for(int i=0; i<(N+1)/2; ++i)
    {
        long long t; scanf("%lld", &t);
        ans += query();
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:31:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N; scanf("%d", &N);
            ~~~~~^~~~~~~~~~
candies.cpp:36:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         long long t; scanf("%lld", &t);
                      ~~~~~^~~~~~~~~~~~
candies.cpp:63:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         long long t; scanf("%lld", &t);
                      ~~~~~^~~~~~~~~~~~

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