Cod sursa(job #425928)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 26 martie 2010 11:49:03
Problema Gardieni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int i,j,n,t,de[100000],dr,st;
long long rez;

struct nod
{
	int a,b,c;
}x[55000];

vector<int> t1[1000005];

//bool comp(nod x,nod y)
//{
	//if(x.a-y.a) return x.a<y.a;
	//return x.b<y.b;
//}

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",&x[i].a,&x[i].b,&x[i].c);
	
	//sort(x+1,x+n+1,comp);
	
	for(i=1;i<=n;++i)
	{
		t1[ x[i].a ].push_back(i);
		t1[ x[i].b+1].push_back(-i);
	}
	dr=0;st=1;
	
	for(i=1;i<=t;++i)
	{
		int m=t1[i].size();
		
		for(j=0;j<m;++j)
		{
			if(t1[i][j]>0)
			{
				int ind=t1[i][j];
				
				while(dr>=st&&x[ind].c<x[ de[dr] ].c) --dr;
				
				de[++dr]=ind;
			}
			
			else 
			{
				int ind=-t1[i][j];
				if(de[st]==ind) st++;
			}
		}
		
		rez=rez+(long long)(x[ de[st] ].c);
	}
	
	printf("%lld\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}