oj.uz

Submission #45085

# Submission time Handle Problem Language Result Execution time Memory
45085 2018-04-11T07:43:28 Z Abelyan Candies (JOI18_candies) C++14
0 / 100
 4 ms 376 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{
	int l, r, val;
	bool nl;
};

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

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		int k;
		scanf("%d", &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 vl = p.top().fr;
		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;
			ans += nd[ind].val;
			nd[ind].nl = true;
		}
		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;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:55:7: warning: unused variable 'vl' [-Wunused-variable]
   int vl = p.top().fr;
       ^~
candies.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
candies.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 92.0

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