Cod sursa(job #1757748)

Utilizator hackerinoHackerino hackerino Data 15 septembrie 2016 19:10:00
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;
ifstream f("hotel.in"); ofstream g("hotel.out");
const int Dmax=300001;
int N,M,A[Dmax],B[Dmax],C[Dmax];
void update(int n, int l, int r, int a, int b, int t){
    if(a<=l && r<=b){
     if(t==1){A[n]=B[n]=C[n]=0;}
     else{A[n]=B[n]=C[n]=r-l+1;}
    }
    else{
     int m=(l+r)>>1,n2=2*n;
     if(A[n]==r-l+1){A[n2]=B[n2]=C[n2]=m-l+1;A[n2+1]=B[n2+1]=C[n2+1]=r-m;}
     if(A[n]==0){A[n2]=B[n2]=C[n2]=0;A[n2+1]=B[n2+1]=C[n2+1]=0;}
     if(a<=m){update(n2,l,m,a,b,t);}
     if(m<b){update (n2+1,m+1,r,a,b,t);}
     if(B[n2]==m-l+1){B[n]=m-l+1+B[n2+1];}
     else{B[n]=B[n2];}
     if(C[n2+1]==r-m){C[n]=r-m+C[n2];}
     else{C[n]=C[n2+1];}
     A[n]=A[n2]>A[n2+1]?A[n2]:A[n2+1];
     if(A[n]<B[n2+1]+C[n2]){A[n]=B[n2+1]+C[n2];}
    }
}
int main(){
 f>>N>>M;
 A[1]=B[1]=C[1]=N;
   while(M--)
    {   int t,a,b;
        f>>t;
        if(t<3) f>>a>>b, update(1,1,N,a,a+b-1,t); else g<<A[1]<<"\n";
    }
    g.close(); return 0;
}