注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-3117: [Noi1999]内存分配(平衡树)  

2014-07-05 16:20:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3117


用一个优先队列来处理时间的关系,然后一个队列存等待队列的东西,内存部分用一棵平衡树维护,这样就可以O(q log q)了。


代码(splay):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <queue>

  •    

  • using namespace std ;

  •    

  • const int maxv = 10100 ;

  •    

  • struct node {

  •         node *lc , *rc , *fa ;

  •         int l , r , maxl , len ;

  •         inline void update(  ) {

  •                 maxl = max( max( lc -> maxl , rc -> maxl ) , len ) ;

  •         }

  • } bst[ maxv ] ;

  •    

  • node *root , *pt = bst , *null ;

  •    

  • int n ;

  •    

  • inline void Init_splay(  ) {

  •         null = pt ++ ;

  •         null -> lc = null -> rc = null -> fa = null , null -> len = null -> maxl = 0 ;

  •         node *l = pt ++ , *r = pt ++ ;

  •         l -> lc = l -> fa = r -> lc = r -> rc = null ;

  •         l -> l = -1 , l -> r = -1 , r -> l = n , r -> r = n , r -> len = 0 , l -> len = n ;

  •         ( l -> rc = r ) -> fa = l ;

  •         ( root = l ) -> update(  ) ;

  • }

  •    

  • #define C( t ) ( t == t -> fa -> lc )

  •    

  • inline void zag( node *t ) {

  •         node *k = t -> rc , *u = t -> fa ; bool flag = C( t ) ;

  •         ( ( t -> rc = k -> lc ) -> fa = t ) -> update(  ) ;

  •         ( ( k -> lc = t ) -> fa = k ) -> update(  ) ;

  •         if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

  • }

  •    

  • inline void zig( node *t ) {

  •         node *k = t -> lc , *u = t -> fa ; bool flag = C( t ) ;

  •         ( ( t -> lc = k -> rc ) -> fa = t ) -> update(  ) ;

  •         ( ( k -> rc = t ) -> fa = k ) -> update(  ) ;

  •         if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

  • }

  •    

  • inline void splay( node *t , node *v ) {

  •         while ( t -> fa != v ) {

  •                 if ( t -> fa -> fa == v ) if ( C( t ) ) zig( t -> fa ) ; else zag( t -> fa ) ; else {

  •                         if ( C( t ) ) {

  •                                 if ( C( t -> fa ) ) zig( t -> fa -> fa ) ; zig( t -> fa ) ;

  •                         } else {

  •                                 if ( ! C( t -> fa ) ) zag( t -> fa -> fa ) ; zag( t -> fa ) ;

  •                         }

  •                 }

  •         }

  •         if ( v == null ) root = t ;

  • }

  •    

  • inline node* select( int L ) {

  •         if ( root -> maxl < L ) return null ;

  •         node *t = root ;

  •         while ( 1 ) {

  •                 if ( t -> lc -> maxl >= L ) t = t -> lc ; else

  •                 if ( t -> len >= L ) break ; else t = t -> rc ;

  •         }

  •         splay( t , null ) ;

  •         return t ;

  • }

  •    

  • struct ntype {

  •         node *t ;

  •         int T ;

  •         ntype( node *_t , int _T ) : t( _t ) , T( _T ) {

  •         }

  •         bool operator < ( const ntype &a ) const {

  •                 return T > a.T ;

  •         }

  • } ;

  • priority_queue < ntype > pq ;

  •    

  • inline bool add( int s , int len , int P ) {

  •         node *pre = select( len ) ;

  •         if ( pre == null ) return false ;

  •         node *suff = pre -> rc ;

  •         for ( ; suff -> lc != null ; suff = suff -> lc ) ;

  •         splay( suff , pre ) ;

  •         node *t = pt ++ ;

  •         t -> lc = t -> rc = null , ( suff -> lc = t ) -> fa = suff ;

  •         t -> l = pre -> r + 1 , t -> r = pre -> r + len ;

  •         t -> len = t -> maxl = suff -> l - t -> r - 1 , pre -> len = 0 ;

  •         suff -> update(  ) ; pre -> update(  ) ;

  •         pq.push( ntype( t , s + P ) ) ;

  •         return true ;

  • }

  •    

  • inline void del( node *t ) {

  •         splay( t , null ) ;

  •         node *pre = t -> lc , *suff = t -> rc ;

  •         for ( ; pre -> rc != null ; pre = pre -> rc ) ;

  •         for ( ; suff -> lc != null ; suff = suff -> lc ) ;

  •         splay( pre , t ) , splay( suff , t ) ;

  •         pre -> len = suff -> l - pre -> r - 1 , pre -> fa = null ;

  •         ( ( pre -> rc = suff ) -> fa = pre ) -> update(  ) ;

  •         root = pre ;

  • }

  •    

  • queue < pair< int , int > > q ;

  •    

  • int cnt = 0 ;

  •    

  • int main(  ) {

  •         scanf( "%d" , &n ) ;

  •         Init_splay(  ) ;

  •         int T , M , P , Time = 0 ;

  •         while ( 1 ) {

  •                 scanf( "%d%d%d" , &T , &M , &P ) ;

  •                 if ( T == 0 && M == 0 && P == 0 ) break ;

  •                 while ( ! pq.empty(  ) ) {

  •                         ntype now = pq.top(  ) ;

  •                         if ( now.T > T ) break ;

  •                         Time = now.T;

  •                         while ( ! pq.empty(  ) ) {

  •                                 now = pq.top(  ) ;

  •                                 if ( now.T == Time ) {

  •                                         del( now.t ) ;

  •                                         pq.pop(  ) ;

  •                                 } else break ;

  •                         }

  •                         pair < int , int > p ;

  •                         while ( ! q.empty(  ) ) {

  •                                 p = q.front(  ) ;

  •                                 if ( ! add( Time , p.first , p.second ) ) break ;

  •                                 q.pop(  ) ;

  •                         }

  •                 }

  •                 Time = T ;

  •                 if ( ! add( T , M , P ) ) {

  •                         ++ cnt , q.push( make_pair( M , P ) ) ;

  •                 }

  •         }

  •         while ( ! pq.empty(  ) ) {

  •                 ntype now = pq.top(  ) ;

  •                 Time = now.T ;

  •                 while ( ! pq.empty(  ) ) {

  •                         now = pq.top(  ) ;

  •                         if ( now.T == Time ) {

  •                                 del( now.t ) ;

  •                                 pq.pop(  ) ;

  •                         } else break ;

  •                 }

  •                 pair < int , int > p ;

  •                 while ( ! q.empty(  ) ) {

  •                         p = q.front(  ) ;

  •                         if ( ! add( Time , p.first , p.second ) ) break ;

  •                         q.pop(  ) ;

  •                 }

  •         }

  •         printf( "%d\n%d\n" , Time , cnt ) ;

  •         return 0 ;

  • }



  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017