Submission #862500

#	Time	Username	Problem	Language	Result	Execution time	Memory
862500		eitanelb	Candies (JOI18_candies)	C++14	0 / 100	2 ms	348 KiB

candies

#include<bits/stdc++.h>
using namespace std;
//#include"nuts.h"

#define ll long long
#define x first
#define y second
#define pi pair<ll,ll>

vector<long long> Nuts(int n, vector<int> v){
    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;
    vector<ll> ans;
    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;
        ans.push_back(res);
        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});
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int> nuts(n);
    for(int i=0;i<n;i++) cin>>nuts[i];
    
    vector<long long> ans = Nuts(n, nuts);
    
    for(long long c : ans) cout<<c<<endl;
    return 0;
}

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