Cod sursa(job #760356)

Utilizator ion824Ion Ureche ion824 Data 21 iunie 2012 01:14:35
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 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[2*nod].lright=A[2*nod].lleft=A[2*nod].lmax=div-left+1; 
     A[2*nod+1].lright=A[2*nod+1].lleft=A[2*nod+1].lmax=right-div;                            
   }
   if(A[nod].lmax==0)
   {
     A[2*nod].lright=A[2*nod].lleft=A[2*nod].lmax=0; 
     A[2*nod+1].lright=A[2*nod+1].lleft=A[2*nod+1].lmax=0;                            
   }
   
   if(st<=div)update(2*nod,left,div);
   if(dr>div)update(2*nod+1,div+1,right);
   
   if(A[2*nod].lleft==div-left+1)A[nod].lleft=A[2*nod].lleft+A[2*nod+1].lleft;
                            else A[nod].lleft=A[2*nod].lleft;
                            
   if(A[2*nod+1].lright==right-div)A[nod].lright=A[2*nod+1].lright+A[2*nod].lright;
                              else A[nod].lright=A[2*nod+1].lright;
                              
   A[nod].lmax = max( A[2*nod].lright+A[2*nod+1].lleft , max( A[2*nod].lmax , A[2*nod+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;   
}