Doce - Seletiva IOI 2014

Doce.cpp

// Doce de Banana - Seletiva IOI 2014
// Complexidade O(N*log(N))
// Matheus Leal V :D

#include <bits/stdc++.h>
#define N 100050
#define int long long
using namespace std;

int n, D[N], P[N], B[N];

struct node
{
	int val, sz, w, qtd, sum, qtd2;

	node *l, *r;

	node(int x = 0, int q = 0)
	{
		w = rand(), val = x, sz = 1, qtd = qtd2 = q, sum = x;

		l = r = NULL;
	}
};

int s(node *root)
{
	return root ? root->sum : 0;
}

int qtdi(node *root)
{
	return root ? root->qtd : 0;
}

int sz(node *root)
{
	return root ? root->sz : 0;
}

void upd(node *&root)
{
	if(!root) return;

	root->sz = sz(root->l) + sz(root->r) + 1;

	root->qtd = qtdi(root->l) + qtdi(root->r) + root->qtd2;

	root->sum = s(root->l) + s(root->r) + (root->qtd2*root->val);
}

void Merge(node *&root, node *l, node *r)
{
	if(!l || !r) root = l ? l : r;

	else
	{
		if(l->w > r->w) Merge(l->r, l->r, r), root = l;

		else Merge(r->l, l, r->l), root = r;
	}

	upd(root);
}

void Split(node *root, node *&l, node *&r, int val)
{
	if(!root) l = r = NULL;
	else
	{
		if(root->val < val) Split(root->r, root->r, r, val), l = root;

		else Split(root->l, l, root->l, val), r = root;
	}

	upd(root);
}

node *root = NULL;

void insert(int x, int qtd)
{
	node *l = NULL, *r = NULL, *novo = new node(x, qtd);

	Split(root, l, r, x);

	Merge(l, l, novo);

	Merge(root, l, r);
}

void Split_2(node *root, node *&l, node *&r, int k)
{
	if(!root) l = r = NULL;
	else
	{
		int QTD_ESQ = qtdi(root->l);

		if(QTD_ESQ >= k)
		{
			Split_2(root->l, l, root->l, k);

			r = root;
		}
		else
		{
			if(QTD_ESQ + root->qtd2 >= k )
			{
				k -= QTD_ESQ;

				if(k != root->qtd2)
				{
					node *novo = new node(root->val, root->qtd2 - k);

					root->qtd2 = k;

					novo->r = root->r;

					upd(novo);

					r = novo;
				}
				else  r = root->r;

				l = root;

				root->r = NULL;
			}

			else Split_2(root->r, root->r, r,  k - root->qtd2 - QTD_ESQ), l = root;
		}
	}

	upd(root);
}

int ans = 0;

bool check = true;

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

	cin>>n;

	for(int i = 1; i <= n; i++) cin>>D[i]>>B[i]>>P[i];

	for(int i = 1; i <= n; i++)
	{
		node *l = NULL, *r = NULL;

		Split_2(root, l, r, D[i]);

		root = l;

		insert(P[i], B[i]);

		if(root && root->qtd < D[i])
		{
			ans = -1;

			break;
		}

		if(check)
		{
			node *l = NULL, *r = NULL;

			Split_2(root, l, r, D[i]);

			int pp = s(l);

			root = r;

			ans += pp;
		}
	}

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