Cod sursa(job #2337785)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 6 februarie 2019 18:32:54
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
 
#define MAXN 100000
 
using namespace std;

ifstream fin( "hotel.in" );
ofstream fout( "hotel.out" );
 
struct Node
{
  int slm;
  int pref;
  int suf;
  int lazy;
  
  Node( )
  {
    ;
  }
  
  Node( int val )
  {
    slm=pref=suf=val;
  }
};
 
Node aint[4*MAXN+5];

inline int maxim( int a, int b )
{
  if( a>b )
    return a;
  else
    return b;
}

void propagate( int poz, int st, int dr )
{
  if( aint[poz].lazy==-1 )
    return;
    
  int mid=(st+dr)/2;
  
  if( aint[poz].lazy==1 )
  {
    aint[2*poz]=Node(0);
    aint[2*poz+1]=Node(0);
  }
  else
  {
    aint[2*poz]=Node(mid-st+1);
    aint[2*poz+1]=Node(dr-mid);
  }
  
  aint[2*poz].lazy=aint[2*poz+1].lazy=aint[poz].lazy;
  
  aint[poz].lazy=-1;
}
 
Node merge( int st, int dr, Node a, Node b )
{
  int mid=(st+dr)/2;
    
  Node aux;
    
  aux.pref=a.pref;
  aux.suf=b.suf;
    
  if( a.pref==mid-st+1 )
    aux.pref+=b.pref;
    
  if( b.suf==dr-mid )
    aux.suf+=a.suf;
        
  aux.slm=maxim(maxim(maxim(a.slm,b.slm),maxim(aux.pref,aux.suf)),a.suf+b.pref);
    
  aux.lazy=-1;
    
  return aux;
}
 
void update( int a, int b, int val, int poz, int st, int dr )
{
  if( b<st || dr<a )
    return;
    
  if( a<=st && dr<=b )
  {
    if( val==1 )
      aint[poz]=Node(0);
    else
      aint[poz]=Node(dr-st+1);
  
    aint[poz].lazy=val;
  }
  else
  {
    int mid=(st+dr)/2;
    
    propagate(poz,st,dr);
    
    update(a,b,val,2*poz,st,mid);
    update(a,b,val,2*poz+1,mid+1,dr);

    aint[poz]=merge(st,dr,aint[2*poz],aint[2*poz+1]);
  }
}
 
int main() // lazy = 1 se ocupa camerele, lazy = 0 se elibereaza camerele, lazy = -1 nu se stie
{
  int n, m;
  
  fin>>n>>m;
    
  update(1,n,0,1,1,n);
  
  for( int i=1;i<=m;i++ )
  {
    int op;
    
    fin>>op;
    
    if( op==3 )
      fout<<aint[1].slm<<'\n';
    else
    {
      int a, b;
    
      fin>>a>>b;
      
      if( op==1 )
        update(a,a+b-1,1,1,1,n);
      else
        update(a,a+b-1,0,1,1,n);
    }
  }

  return 0;
}