Submission #49866

#	Time	Username	Problem	Language	Result	Execution time	Memory
49866		MatheusLealV	Candies (JOI18_candies)	C++17	100 / 100	619 ms	76196 KiB

candies

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

int n, k, v[N], ans, t = 0;

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)
	{
		if( p <= 0 || p > n ) return;

		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);

		if(l > 0 && l <= n && r > 0 && r <= n) v[id] = -v[id] + v[l] + v[r];

		else v[id] = -inf;

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

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

		ans += x;

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

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