Cod sursa(job #126738)

Utilizator razvi9Jurca Razvan razvi9 Data 22 ianuarie 2008 19:12:56
Problema Gardieni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
int a,b,c,n,i,j,t;
typedef struct nod
{int c;
nod *st,*dr;}nod;
nod *p;

nod* new_nod(int c)
{nod *t;
 t=new nod;
 t->c=c;
 t->st=t->dr=NULL;
 return t;}

void add(int a,int b,int c,int st,int dr,nod *p)
{if(a>dr||b<st) return;
 if(a<st) a=st;
 if(b>dr) b=dr;
 if(p->c && p->c<=c) return;

 int mij=(st+dr)/2;

 if(a==st && b==dr)
  if(!p->st) {p->c=c;return;}
 if(!p->st)
 {p->st=new_nod(p->c);
  p->dr=new_nod(p->c);}
 p->c=0;
 add(a,b,c,st,mij,p->st);
 add(a,b,c,mij+1,dr,p->dr);}

long long get_cost(nod *p)
{if(p->c) return p->c;                                  
 return get_cost(p->st)+get_cost(p->dr);}

int main()
{freopen("gardieni.in","r",stdin);
 freopen("gardieni.out","w",stdout);
 scanf("%d %d",&n,&t);
 p=new_nod(0);

 for(i=1;i<=n;i++)
  {scanf("%d %d %d",&a,&b,&c);
   add(a,b,c,1,t,p);}
 printf("%lld",get_cost(p));
 fclose(stdout);
 return 0;}