Cod sursa(job #124986)

Utilizator znakeuJurba Andrei znakeu Data 20 ianuarie 2008 10:46:07
Problema Gardieni Scor 50
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 10-a Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>

struct interval
{
	int a,b,c;
};

int n,t,k,k2;
long long s=0;
interval v1[50006];
interval v2[50006];


int comp(const void *a, const void *b)
{
	interval *aa=(interval*) a, *bb=(interval*) b;
	interval x=*aa, y=*bb;
	return x.c-y.c;
}

int main()
{
	int i,j,tmp;
	
	FILE *in  = fopen("gardieni.in","r");
	FILE *out = fopen("gardieni.out","w");
	
	fscanf(in,"%d%d",&n,&t);
	
	for (i=0; i<n; i++)
		fscanf(in,"%d%d%d",&v1[i].a,&v1[i].b,&v1[i].c);
	qsort(v1,n,sizeof(v1[0]),comp);
	
	v2[0].a=1;
	v2[0].b=t;
	k=1; k2=1;
	
	for (i=0; i<n && k2; i++)
	{
		for (j=0; j<k; j++)
			if (v2[j].c==0)
			{
				tmp=0;
//			[--------]
//				[--------]
				if (v1[i].a<=v2[j].a && v1[i].b>=v2[j].a && v1[i].b<=v2[j].b && tmp==0)
				{
					s+=v1[i].c*(v1[i].b-v2[j].a+1);
					v2[j].a=v1[i].b+1;
					if (v2[j].a>v2[j].b)
					{
						v2[j].c=-1;
						k2--;
					}
					tmp=1;
				}
//			[----------------]
//				[--------]
				if (v1[i].a<=v2[j].a && v1[i].b>=v2[j].b && tmp==0)
				{
					s+=v1[i].c*(v2[j].b-v2[j].a+1);
					v2[j].c=-1;
					k2--;
					tmp=1;
				}
//					[--------]
//				[--------]
				if (v1[i].a>=v2[j].a && v1[i].a<=v2[j].b && v1[i].b>=v2[j].b && tmp==0)
				{
					s+=v1[i].c*(v2[j].b-v1[i].a+1);
					v2[j].b=v1[i].a-1;
					if (v2[j].a>v2[j].b)
					{
						v2[j].c=-1;
						k2--;
					}
					tmp=1;
				}
//		  		  [----]
//				[--------]
				if (v1[i].a>v2[j].a && v1[i].b<v2[j].b && tmp==0)
				{
					s+=v1[i].c*(v1[i].b-v1[i].a+1);
					v2[k].b=v2[j].b;
					v2[j].b=v1[i].a-1;
					v2[k].a=v1[i].b+1;
					k++;
					k2++;					
					tmp=1;
				}
			}
	}
	fprintf(out,"%lld\n",s);
	
	fclose(in);
	fclose(out);
	
	return 0;
}