Submission #45002

#	Time	Username	Problem	Language	Result	Execution time	Memory
45002		bogdan10bos	Candies (JOI18_candies)	C++14	100 / 100	688 ms	20652 KiB

candies

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;
typedef pair<LL, int> pii;

LL sum[200005];
int N;
int v[200005];
int nxt[200005], prv[200005];
int st[200005], dr[200005];

set<pii> s;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &v[i]);
        sum[i] = sum[i - 1] + ( (i & 1) ? v[i] : -v[i] );
        nxt[i] = i + 1;
        prv[i] = i - 1;
        st[i] = dr[i] = i;
        s.insert({v[i], i});
    }

    LL ans = 0;
    for(int i = 1; i <= (N + 1) / 2; i++)
    {
        auto it = s.end();
        it--;
        LL val = (*it).first;
        int pos = (*it).second;
        s.erase(it);

        ans += val;
        printf("%lld\n", ans);

        if(i == (N + 1) / 2)    break;

        int p = prv[pos];
        int u = nxt[pos];
        int cnt = 0;
        if(p != 0)
        {
            cnt++;
            LL val = sum[ dr[p] ] - sum[ st[p] - 1 ];
            if(st[p] % 2 == 0)  val = -val;
            s.erase({val, p});

            nxt[ prv[p] ] = pos;
            prv[pos] = prv[p];
            st[pos] = st[p];
        }
        if(u != N + 1)
        {
            cnt++;
            LL val = sum[ dr[u] ] - sum[ st[u] - 1 ];
            if(st[u] % 2 == 0)  val = -val;
            s.erase({val, u});

            prv[ nxt[u] ] = pos;
            nxt[pos] = nxt[u];
            dr[pos] = dr[u];
        }

        if(cnt == 2)
        {
            LL val = sum[ dr[pos] ] - sum[ st[pos] - 1 ];
            if(st[pos] % 2 == 0)    val = -val;
            s.insert({val, pos});
        }
        else
        {
            prv[ nxt[pos] ] = prv[pos];
            nxt[ prv[pos] ] = nxt[pos];
        }
    }

    return 0;
}

Compilation message (stderr)

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

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