Cod sursa(job #125319)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 20 ianuarie 2008 12:34:30
Problema Gardieni Scor 70
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 10-a Marime 1.18 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;
const int n_max = 50010;
set < pair < int, int> > s;
set < pair < int, int> >::iterator it;
int a[n_max],
	b[n_max],
	c[n_max],
	ind[n_max];
int i, t, p, n, minim;
long long sol;
bool cmp(const int x, const int y)
{
	if (a[x] == a[y])
		return b[x] < b[y];
	return a[x] < a[y];
}
int main()
{
	freopen("gardieni.in","r",stdin);
	freopen("gardieni.out","w",stdout);
	scanf("%d %d", &n, &t);
	for (i = 1; i <= n; ++ i)
	{
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
		ind[i] = i;
	}
	p = 1;
	sort(ind + 1, ind + n +1, cmp);
//	fprintf(stderr,"Am terminat soratarea\n");
	for (i = 1; i <= t; ++ i)
	{
/*		if (i%10 == 0)
			fprintf(stderr, "%d\n", i);
*/		while (a[ind[p]]<=i && p <=n)
		{
			s.insert(make_pair(b[ind[p]], ind[p]));
			++p;
		}
		it = s.begin();
		
		while (it->first < i && s.size()>0)
		{
		
			s.erase(make_pair(it->first, it->second));
			it = s.begin();
		}
		minim = 1<<30;
		
		for (it = s.begin(); it != s.end(); ++ it)
		{
			if (c[it->second] < minim)
				minim = c[it->second];
		}
		sol =sol + minim;
	}
	printf("%lld\n", sol);
	return 0;
}