Cod sursa(job #760357)

Utilizator ion824Ion Ureche ion824 Data 21 iunie 2012 01:21:37
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
using namespace std;

struct a{
       int lleft,lright,lmax;
       }A[300003];      
int st,dr,val,cod;
      
inline int max(int a,int b){ return a>b?a:b; }
      
void init(int nod,int left,int right){
     A[nod].lleft=A[nod].lright=A[nod].lmax=right-left+1;
     if(left==right)return ;
     int div=(left+right)>>1;
     init(2*nod,left,div);
     init(2*nod+1,div+1,right);     
     }      
      
void update(int nod,int left,int right){
   if(st<=left && right<=dr){
           int val;
           if(cod)val=right-left+1;
             else val=0;
           A[nod].lleft=A[nod].lright=A[nod].lmax=val;   
           return ;
                         }
   int div=(left+right)>>1;
   
   if(A[nod].lmax==right-left+1)
   {
     A[nod<<1].lright=A[nod<<1].lleft=A[nod<<1].lmax=div-left+1; 
     A[(nod<<1)+1].lright=A[(nod<<1)+1].lleft=A[(nod<<1)+1].lmax=right-div;                            
   }
   if(A[nod].lmax==0)
   {
     A[nod<<1].lright=A[nod<<1].lleft=A[nod<<1].lmax=0; 
     A[(nod<<1)+1].lright=A[(nod<<1)+1].lleft=A[(nod<<1)+1].lmax=0;                            
   }
   
   if(st<=div)update(2*nod,left,div);
   if(dr>div)update(2*nod+1,div+1,right);
   
   if(A[nod<<1].lleft==div-left+1)A[nod].lleft=A[nod<<1].lleft+A[(nod<<1)+1].lleft;
                            else A[nod].lleft=A[nod<<1].lleft;
                            
   if(A[(nod<<1)+1].lright==right-div)A[nod].lright=A[(nod<<1)+1].lright+A[nod<<1].lright;
                              else A[nod].lright=A[(nod<<1)+1].lright;
                              
   A[nod].lmax = max( A[nod<<1].lright+A[(nod<<1)+1].lleft , max( A[nod<<1].lmax , A[(nod<<1)+1].lmax ) );
     }
               
int main(void){
    ifstream fin("hotel.in");
    ofstream fout("hotel.out");
    int n,m,i;
    fin>>n>>m; 
    init(1,1,n);              

    for(i=1;i<=m;++i)
    {
     fin>>cod;
     if(cod==3)fout<<A[1].lmax<<'\n';
       else{
            fin>>st>>dr; dr=st+dr-1;
            cod--;
            update(1,1,n);
            }                      
    }
 return 0;   
}