oj.uz

Submission #45091

# Submission time Handle Problem Language Result Execution time Memory
45091 2018-04-11T08:06:22 Z Abelyan Candies (JOI18_candies) C++14
0 / 100
 5 ms 504 KB 
#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{
	long long l, r, val;
	bool nl;
};

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

int main(){
	long long n;
	cin >> n;
	for (long long i = 0; i < n; i++){
		long long 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));
	}
	long long counter = n;
	long long ans = 0;
	while (!p.empty()){
		long long 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -