Submission #961011

#	Time	Username	Problem	Language	Result	Execution time	Memory
961011		pcc	Candies (JOI18_candies)	C++17	100 / 100	83 ms	20420 KiB

candies

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll mxn = 4e5+10;

struct node{
	int pl,pr;
	ll val;
	node(){}
};

node lst[mxn];
int ppp = 0;

int newnode(){
	return ++ppp;
}

int N;
ll arr[mxn];
ll ans[mxn];
priority_queue<pll,vector<pll>,less<pll>> pq;
bitset<mxn> dead;

void del(int now){
	int ls = lst[now].pl,rs = lst[now].pr;
	lst[ls].pr = rs;
	lst[rs].pl = ls;
	dead[now] = true;
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	int pre = 0;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		int tmp = newnode();
		lst[tmp].pl = pre;
		lst[pre].pr = tmp;
		lst[tmp].val = arr[i];
		pre = tmp;
	}
	for(int i = 1;i<=N;i++){
		pq.push(pll(lst[i].val,i));
	}
	for(int i = 1;i<=(N+1)/2;i++){
		while(dead[pq.top().sc])pq.pop();
		ans[i] = ans[i-1];
		auto now = pq.top().sc;pq.pop();
		ans[i] += lst[now].val;
		int ls = lst[now].pl,rs = lst[now].pr;
		del(now);
		if(ls)del(ls);
		if(rs)del(rs);
		if(!ls||!rs)continue;
		int tmp = newnode();
		lst[tmp].val = lst[ls].val+lst[rs].val-lst[now].val;
		ls = lst[ls].pl,rs = lst[rs].pr;
		lst[tmp].pl = ls;lst[ls].pr = tmp;
		lst[tmp].pr = rs;lst[rs].pl = tmp;
		pq.push(pll(lst[tmp].val,tmp));
	}
	for(int i = 1;i<=(N+1)/2;i++)cout<<ans[i]<<'\n';
	return 0;
}

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