Cod sursa(job #126756)

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

int a,b,c,n,i,j,t;
nod *p;

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

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)
 {new_nod(p->st,p->c);
  new_nod(p->dr,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 || !p->st) 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);
 new_nod(p,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;}