Submission #45015

#	Time	Username	Problem	Language	Result	Execution time	Memory
45015		SpaimaCarpatilor	Candies (JOI18_candies)	C++17	100 / 100	310 ms	13100 KiB

candies

#include<bits/stdc++.h>

using namespace std;

int N, a[200009], t[200009], id[200009], lft[200009], rgt[200009], isActive[200009];
long long s[200009];
bool canTake[200009], taken[200009];
set < pair < long long, int > > S;

bool cmp (int i, int j)
{
    return a[i] > a[j];
}

int tata (int x)
{
    if (t[x] == x) return x;
    return t[x] = tata (t[x]);
}

long long extraP[200009];
void refresh (int root)
{
    S.erase ({extraP[root], root});
    int r = rgt[root], l = lft[root];
    if (r < N && l > 1)
    {
        long long ld = s[r] - s[l - 2], nw = s[r + 1] - (l >= 3 ? s[l - 3] : 0);
        extraP[root] = nw - ld, S.insert ({extraP[root], root});
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=1; i<=N; i++)
    scanf ("%d", &a[i]), s[i] = a[i] + (i > 2 ? s[i - 2] : 0), id[i] = i, canTake[i] = 1, taken[i] = 0;
sort (id + 1, id + N + 1, cmp);
int pntr = 1;
long long ans = 0;
for (int K=1; K<=(N + 1) / 2; K++)
{
/*    printf ("%d: ", K);
    for (auto it : S)
        printf ("(%lld, %d) ", it.first, it.second);*/
    while (!S.empty () && isActive[S.rbegin ()->second] == 0)
    {
//        printf ("del (%d) ", S.rbegin ()->second);
        auto it = S.end (); it --;
        S.erase (it);
    }
//    printf ("\n");
    while (!canTake[id[pntr]] && pntr <= N) pntr ++;
    long long price1 = (pntr > N ? -1LL << 60 : (long long) a[id[pntr]]), price2 = (S.empty () ? -1LL << 60 : S.rbegin ()->first);
    if (price1 > price2)
    {
        ans += price1;
        int pos = id[pntr];
    //    printf ("add %d\n", pos);
        taken[pos] = 1, canTake[pos] = canTake[pos - 1] = canTake[pos + 1] = 0;
        if (pos >= 2 && t[pos - 2] > 0 && t[pos + 2] > 0)
        {
            int r1 = tata (t[pos - 2]), r2 = tata (t[pos + 2]);
            t[r2] = t[pos] = r1, isActive[r2] = 0;
            rgt[r1] = rgt[r2], refresh (r1);
        }
        else
        if (pos >= 2 && t[pos - 2] > 0)
        {
            int r = tata (pos - 2);
            t[pos] = r, rgt[r] = pos, refresh (r);
        }
        else
        if (t[pos + 2] > 0)
        {
            int r = tata (pos + 2);
            t[pos] = r, lft[r] = pos, refresh (r);
        }
        else t[pos] = pos, isActive[pos] = 1, lft[pos] = rgt[pos] = pos, refresh (pos);
    }
    else
    {
        ans += price2;
        int root = S.rbegin ()->second;
        //printf ("extend %d [%d, %d] -> ", root, lft[root], rgt[root]);
        lft[root] --, rgt[root] ++;
        t[lft[root]] = t[rgt[root]] = root;
        canTake[lft[root] - 1] = canTake[rgt[root] + 1] = 0;
        if (lft[root] - 2 >= 1 && t[lft[root] - 2] > 0)
        {
            int r1 = tata (lft[root] - 2);
            t[r1] = root, lft[root] = lft[r1], isActive[r1] = 0;
        }
        if (t[rgt[root] + 2] > 0)
        {
            int r2 = tata (rgt[root] + 2);
            t[r2] = root, rgt[root] = rgt[r2], isActive[r2] = 0;
        }
        //printf ("[%d %d]\n", lft[root], rgt[root]);
        refresh (root);
    }
/*    printf ("segms: ");
    set < pair < int, int > > ss;
    for (int i=1; i<=N; i++)
    if(t[i]>0)
    {
        int q=tata(i);
        ss.insert({lft[q], rgt[q]});
    }
    for(auto it:ss)
        printf("[%d, %d]",it.first, it.second);
    printf ("\n");*/
/*    for (int i=1; i<=N; i++)
        if (canTake[i]) printf ("1");
        else printf ("0");
    printf ("\n");*/
    printf ("%lld\n", ans);
}

return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
candies.cpp:40:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &a[i]), s[i] = a[i] + (i > 2 ? s[i - 2] : 0), id[i] = i, canTake[i] = 1, taken[i] = 0;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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