Submission #861127

#	Time	Username	Problem	Language	Result	Execution time	Memory
861127		eitanelb	Candies (JOI18_candies)	C++14	100 / 100	205 ms	12796 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define pi pair<ll,ll>

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll n; cin>>n;
    vector<ll> v(n); for(ll &i : v) cin>>i;
    ll k = (n+1)/2;
    priority_queue<pi> pq;
    ll l[n],r[n];
    for(ll i=0;i<n;i++){
        pq.push({v[i],i});
        l[i]=i-1;r[i]=i+1;
    }
    vector<bool> vis(n,0);
    ll res=0;
    for(ll i=0; i< (n+1)/2;i++){
        while(vis[pq.top().y]) pq.pop();
        pi p = pq.top(); pq.pop();
        res += p.x;
        cout<<res<<endl;
        ll cur = p.y;
        if(r[cur]==n){
            vis[cur]=1;
            if(l[cur]!=-1)vis[l[cur]]=1;
            if(l[l[cur]] > -1) r[l[l[cur]]]=n;
        }
        else if(l[cur]==-1){
            vis[cur]=1;
            if(r[cur]!=n)vis[r[cur]]=1;
            if(r[r[cur]] < n) l[r[r[cur]]]=-1;
        }
        else{
            v[cur] = v[r[cur]]+v[l[cur]] - v[cur];
            vis[r[cur]]=1;
            r[cur] = r[r[cur]];
            if(r[cur] != n) l[r[cur]]=cur;
            vis[l[cur]]=1;
            l[cur] = l[l[cur]];
            if(l[cur] != -1) r[l[cur]]=cur;
            pq.push({v[cur],cur});
        }
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:12:8: warning: unused variable 'k' [-Wunused-variable]
   12 |     ll k = (n+1)/2;
      |        ^

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