Pagini recente » Cod sursa (job #2695178) | Cod sursa (job #2207597) | Cod sursa (job #1669314) | Cod sursa (job #1985366) | Cod sursa (job #124986)
Cod sursa(job #124986)
#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;
}