Cod sursa(job #425940)

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

using namespace std;

int i,j,n,t,de[100000],dr,st;
int 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 if(t1[i][j]<0)
			{
				int ind=-t1[i][j];
				if(de[st]==ind) st++;
			}
		}
		
		rez+=x[ de[st] ].c;
	}
	
	printf("%d\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}