【POJ】3667 Hotel

  1 #include<cstdio>
  2 #define MAX(a,b) ((a)>(b)?(a):(b))
  3 #define MAXN 50010
  4 struct node
  5 {
  6     int right,left,val;
  7 };
  8 node tree[MAXN<<2];
  9 int lazy[MAXN<<2];
 10 void Build(int L,int R,int rt)
 11 {
 12     lazy[rt]=-1;
 13     tree[rt].left=tree[rt].right=tree[rt].val=R-L+1;
 14     if(L!=R)
 15     {
 16         int mid=(L+R)>>1;
 17         Build(L,mid,rt<<1);
 18         Build(mid+1,R,rt<<1|1);
 19     }
 20 }
 21 inline void PushDown(int mid,int L,int R,int rt)
 22 {
 23     if(lazy[rt]!=-1)
 24     {
 25         lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
 26         lazy[rt]^=1;
 27         tree[rt<<1].left=tree[rt<<1].right=tree[rt<<1].val=(mid-L+1)*lazy[rt];
 28         tree[rt<<1|1].left=tree[rt<<1|1].right=tree[rt<<1|1].val=(R-mid)*lazy[rt];
 29         lazy[rt]=-1;
 30     }
 31 }
 32 int Query(int x,int L,int R,int rt)
 33 {
 34     if(L==R)
 35         return L;
 36     int mid=(L+R)>>1;
 37     PushDown(mid,L,R,rt);
 38     if(tree[rt<<1].val>=x)
 39         return Query(x,L,mid,rt<<1);
 40     else if(tree[rt<<1].right+tree[rt<<1|1].left>=x)
 41         return mid-tree[rt<<1].right+1;
 42     else
 43         return Query(x,mid+1,R,rt<<1|1);
 44 }
 45 inline void PushUp(int mid,int L,int R,int rt)
 46 {
 47     tree[rt].left=tree[rt<<1].left;
 48     tree[rt].right=tree[rt<<1|1].right;
 49     if(tree[rt].left==mid-L+1)
 50         tree[rt].left+=tree[rt<<1|1].left;
 51     if(tree[rt].right==R-mid)
 52         tree[rt].right+=tree[rt<<1].right;
 53     tree[rt].val=MAX(tree[rt<<1].val,tree[rt<<1|1].val);
 54     tree[rt].val=MAX(tree[rt].val,tree[rt<<1].right+tree[rt<<1|1].left);
 55 }
 56 void Update(int x,int y,int val,int L,int R,int rt)
 57 {
 58     if(x<=L&&R<=y)
 59     {
 60         lazy[rt]=val;
 61         tree[rt].left=tree[rt].right=tree[rt].val=(R-L+1)*(val^1);
 62     }
 63     else
 64     {
 65         int mid=(L+R)>>1;
 66         PushDown(mid,L,R,rt);
 67         if(mid>=x)
 68             Update(x,y,val,L,mid,rt<<1);
 69         if(y>mid)
 70             Update(x,y,val,mid+1,R,rt<<1|1);
 71         PushUp(mid,L,R,rt);
 72     }
 73 }
 74 int main()
 75 {
 76     int n,m,type,x,y;
 77     while(~scanf("%d%d",&n,&m))
 78     {
 79         Build(1,n,1);
 80         while(m--)
 81         {
 82             scanf("%d%d",&type,&x);
 83             if(type==1)
 84             {
 85                 if(tree[1].val<x)
 86                     puts("0");
 87                 else
 88                 {
 89                     y=Query(x,1,n,1);
 90                     printf("%d\n",y);
 91                     Update(y,y+x-1,1,1,n,1);
 92                 }
 93             }
 94             else
 95             {
 96                 scanf("%d",&y);
 97                 Update(x,x+y-1,0,1,n,1);
 98             }
 99         }
100     }
101     return 0;
102 }
新博客：www.zhixiangli.com