Cod sursa(job #125037)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 20 ianuarie 2008 11:05:43
Problema Gardieni Scor 90
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 10-a Marime 0.74 kb
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

#define MAXT 1000005
#define MAXN 50005

int N, T;
vector<int> ev[MAXT];
int Cst[MAXN];

set< pair<int, int> > cur;

int main()
{
	freopen("gardieni.in", "rt", stdin);
	freopen("gardieni.out", "wt", stdout);

	scanf("%d %d", &N, &T);
	for (int i = 1; i <= N; i++)
	{
		int L, R;
		scanf("%d %d %d", &L, &R, Cst + i);
		ev[L].push_back(i);
		ev[R + 1].push_back(-i);
	}

	long long S = 0;
	for (int i = 1; i <= T; i++)
	{
		for (size_t k = 0; k < ev[i].size(); k++)
			if (ev[i][k] > 0)
				cur.insert( make_pair( Cst[ ev[i][k] ], ev[i][k] ) );
			else
				cur.erase( make_pair( Cst[ -ev[i][k] ], -ev[i][k] ) );

		S += (*cur.begin()).first;
	}
	printf("%lld\n", S);

	return 0;
}