Submission #203819

#	Time	Username	Problem	Language	Result	Execution time	Memory
203819		ho94949	Candies (JOI18_candies)	C++17	100 / 100	261 ms	14624 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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N; cin >> N;
    set<int> S;
    setv(0, -INF); S.insert(0);
    for(int i=1; i<=N; ++i)
    {
        long long t; cin >> 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; cin >> t;
        ans += query();
        cout << ans << '\n';
    }
    return 0;
}

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