Submission #45090

#	Time	Username	Problem	Language	Result	Execution time	Memory
45090		Abelyan	Candies (JOI18_candies)	C++14	0 / 100	6 ms	376 KiB

candies

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <random>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <errno.h>
using namespace std;

#define fr first
#define sc second
#define mpr make_pair

struct node{
	int l, r, val;
	bool nl;
};

const int N = 200006;
priority_queue < pair<int, int> > p;
node nd[4 * N];

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int k;
		cin >> k;
		if (i == 0){
			nd[0].l = -1;
			nd[0].r = 1;
		}
		else if (i==n-1){
			nd[i].l = i - 1;
			nd[i].r = -1;
		}
		else{
			nd[i].l = i - 1;
			nd[i].r = i + 1;
		}
		nd[i].val = k;
		p.push(mpr(k, i));
	}
	int counter = n;
	int ans = 0;
	while (!p.empty()){
		int ind = p.top().sc;
		if (nd[ind].nl){
			p.pop();
			continue;
		}
		if (nd[ind].l == -1 && nd[ind].r == -1){
			ans += nd[ind].val;
			nd[ind].nl = true;
		}
		else if (nd[ind].l == -1 || nd[ind].r == -1){
			nd[ind].l == -1 ? nd[nd[ind].r].l = -1 : nd[nd[ind].l].r = -1;
			if (nd[ind].l == -1){
				nd[nd[ind].r].nl = true; 
				nd[counter].val = nd[nd[ind].r].val - nd[ind].val;
				nd[counter].l = -1;
				nd[counter].r = nd[nd[ind].r].r;
				if (nd[counter].r >= 0){
					nd[nd[counter].r].l = counter;
				}
			}
			else{
				nd[nd[ind].l].nl = true;
				nd[counter].val = nd[nd[ind].l].val - nd[ind].val;
				nd[counter].r = -1;
				nd[counter].l = nd[nd[ind].l].l;
				if (nd[counter].l >= 0){
					nd[nd[counter].l].r = counter;
				}
			}
			p.push(mpr(nd[counter].val, counter));
			ans += nd[ind].val;
			nd[ind].nl = true;
			counter++;
		}
		else{
			ans += nd[ind].val;
			nd[counter].val = nd[nd[ind].l].val + nd[nd[ind].r].val - nd[ind].val;
			nd[counter].l = nd[nd[ind].l].l;
			nd[counter].r = nd[nd[ind].r].r;
			if (nd[counter].r >= 0){
				nd[nd[counter].r].l = counter;
			}
			if (nd[counter].l >= 0){
				nd[nd[counter].l].r = counter;
			}
			nd[nd[ind].l].nl = true;
			nd[nd[ind].r].nl = true;
			nd[ind].nl = true;
			p.push(mpr(nd[counter].val, counter));
			counter++;
		}
		cout << ans << endl;
		p.pop();
	}
	return 0;
}

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