xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

struct  Node{
    
int  a,b,Max,cover;
    
int  lc,rc;
}Tree[
150000 ];
int  C,S,R;
int  Tot;
inline 
int  max( int  a, int  b){
    
return  a > b ? a:b;
}
void  build( int  l, int  r){
    Tot
++ ;
    
int  Now = Tot;
    Tree[Now].a
= l;
    Tree[Now].b
= r;
    Tree[Now].Max
= 0 ;
    Tree[Now].cover
= 0 ;
    
if (r - l > 1 ){
        
int  mid = (l + r) >> 1 ;
        Tree[Now].lc
= Tot + 1 ;
        build(l,mid);
        Tree[Now].rc
= Tot + 1 ;
        build(mid,r);
    }
}
void  insert( int  Num, int  l, int  r, int  v){
    
if (l <= Tree[Num].a && r >= Tree[Num].b){
        Tree[Num].cover
+= v;
        Tree[Num].Max
+= v;
        
return  ;
    }
    
int  mid = (Tree[Num].a + Tree[Num].b) >> 1 ;
    
if (r <= mid) insert(Tree[Num].lc,l,r,v);
    
else   if (l >= mid) insert(Tree[Num].rc,l,r,v);
    
else {
        insert(Tree[Num].lc,l,r,v);
        insert(Tree[Num].rc,l,r,v);
    }
    Tree[Num].Max
= max(Tree[Tree[Num].lc].Max,Tree[Tree[Num].rc].Max) + Tree[Num].cover;
}
bool  query( int  Num, int  l, int  r, int  v, int  s){
    
if (Tree[Num].b - Tree[Num].a == 1 ){
        
if (s - Tree[Num].Max >= v)
            
return   1 ;
        
else  
            
return   0 ;
    }
    
if (s - Tree[Num].Max >= v)  return   1 ;
    
int  mid = (Tree[Num].a + Tree[Num].b) >> 1 ;
    
if (r <= mid)  return  query(Tree[Num].lc,l,r,v,s - Tree[Num].cover);
    
else   if (l >= mid)  return  query(Tree[Num].rc,l,r,v,s - Tree[Num].cover);
    
else {
        
return  query(Tree[Num].lc,l,mid,v,s - Tree[Num].cover) &&
                    query(Tree[Num].rc,mid,r,v,s
- Tree[Num].cover);
    }
}
int  main()
{
    freopen(
" railway.in " , " r " ,stdin);
    freopen(
" railway.out " , " w " ,stdout);
    scanf(
" %d%d%d " , & C, & S, & R);
    Tot
= 0 ;
    build(
0 ,C - 1 );
    
for ( int  i = 1 ;i <= R; ++ i){
        
int  a,b,c;
        scanf(
" %d%d%d " , & a, & b, & c);
        
if (query( 1 ,a - 1 ,b - 1 ,c,S)){
            printf(
" YES\n " );
            insert(
1 ,a - 1 ,b - 1 ,c);
        }
        
else  printf( " NO\n " );
    }
    
return   0 ;
}




posted on 2009-04-25 21:09 xfstart07 阅读(134) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理