Cod sursa(job #125176)

Utilizator razvi9Jurca Razvan razvi9 Data 20 ianuarie 2008 11:52:28
Problema Gardieni Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 10-a Marime 0.9 kb
#include<stdio.h>
int a[50010],b[50010],c[50010],aux,n,i,j,k,t,min,min2;
long long cost;
int poz(int i,int j)
{int x=0,y=-1;
 while(i<j)
 {if(a[i]>a[j]||(a[i]==a[j]&&b[i]>b[j]))
   {aux=x;x=-y,y=-aux;
    aux=a[i];a[i]=a[j];a[j]=aux;
    aux=b[i];b[i]=b[j];b[j]=aux;
    aux=c[i];c[i]=c[j];c[j]=aux;}
  i=i+x;j=j+y;}
 return i;}

void sort(int i,int j)
{if(i>=j) return;
 int k=poz(i,j);
 sort(i,k-1);
 sort(k+1,j);}

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",&a[i],&b[i],&c[i]);
 sort(1,n);
 j=1;i=1;
 while(j<=t)
 {min=c[i]; min2=b[i];
  for(k=i+1;k<=n&&a[k]<=j;k++) {
    if(min>c[k]) min=c[k];
    if(b[k]<min2) min2=b[k];}
  if(k<=n&&a[k]-1<min2) min2=a[k]-1;
  cost=cost+min*(min2+1-j);
  j=min2+1;
  while(j>b[i]&&i<n) i++;}
 printf("%lld",cost);
 fclose(stdout);
 return 0;}