Submission #407055

#	Time	Username	Problem	Language	Result	Execution time	Memory
407055		azberjibiou	Candies (JOI18_candies)	C++17	100 / 100	165 ms	12608 KiB

candies

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=202000;
const int mxM=104;
const int mxK=1000000;
const ll MOD=1000000007;
const ll INF=100000000000001;
typedef struct rng{
    int l, r;
    ll val;
}rng;
typedef struct cmp1{
    bool operator()(rng a, rng b)
    {
        return a.val<b.val;
    }
}cmp1;
int N;
ll A[mxN];
priority_queue <rng, vector<rng>, cmp1> pq;
int par[mxN];
rng uf[mxN];
ll ans;
int L, R;
int findpar(int a)
{
    return par[a]==a ? a : (par[a]=findpar(par[a]));
}
int main()
{
    gibon
    cin >> N;
    for(int i=1;i<=N;i++)   cin >> A[i];
    L=0, R=N+1;
    for(int i=1;i<=N;i++)
    {
        par[i]=i;
        uf[i].l=uf[i].r=i, uf[i].val=A[i];
        pq.push(uf[i]);
    }
    for(int i=1;i<=(N+1)/2;i++)
    {
        while(true)
        {
            rng now=pq.top();
            pq.pop();
            int ncur=findpar(now.l);
            if(uf[ncur].l!=now.l || uf[ncur].r!=now.r || uf[ncur].l<=L || uf[ncur].r>=R)  continue;
            ans+=now.val;
            uf[ncur].val*=-1;
            cout << ans << '\n';
            if(i==(N+1)/2)  break;
            if(uf[ncur].l==L+1)
            {
                L=uf[findpar(uf[ncur].r+1)].r;
                break;
            }
            if(uf[ncur].r==R-1)
            {
                R=uf[findpar(uf[ncur].l-1)].l;
                break;
            }
            int lc=findpar(uf[ncur].l-1);
            par[lc]=ncur;
            uf[ncur].val+=uf[lc].val;
            uf[ncur].l=uf[lc].l;
            int rc=findpar(uf[ncur].r+1);
            par[rc]=ncur;
            uf[ncur].val+=uf[rc].val;
            uf[ncur].r=uf[rc].r;
            pq.push(uf[ncur]);
            break;
        }
    }
}

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