Submission #49865

#	Time	Username	Problem	Language	Result	Execution time	Memory
49865		MatheusLealV	Candies (JOI18_candies)	C++17	0 / 100	3 ms	504 KiB

candies

#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
#define int long long
typedef pair<int, int> pii;

int n, v[N], ans;

set < pii > pq, list;

struct linked_list
{
	int esq[N], dir[N];

	void clear()
	{
		memset(esq, 0, sizeof esq);

		memset(dir, 0, sizeof dir);
	}

	void erase(int p)
	{
		dir[esq[p]] = dir[p];

		esq[dir[p]] = esq[p];
	}
} L;

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		L.esq[i] = i - 1;

		L.dir[i] = i + 1;

		pq.insert({-v[i], i});
	}

	for(int i = 1; i <= ((n + 1)/2); i++)
	{
		auto it = pq.begin();

		int x = -(*it).f, id = (*it).s;

		int l = L.esq[id], r = L.dir[id];

		L.erase(l), L.erase(r);

		int novo = -v[id] + v[l] + v[r];

		pq.erase({-x, id}), pq.erase({-v[l], l}), pq.erase({-v[r], r});

		pq.insert({-novo, id});

		ans += x;

		v[id] = novo;

		cout<<ans<<"\n";
	}
}

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