Cod sursa(job #1964753)

Utilizator Mihai9Oniga Mihai Mihai9 Data 13 aprilie 2017 17:29:23
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 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 up(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){up(n2,l,m,a,b,t);}
  if(m<b){up(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,up(1,1,N,a,a+b-1,t);else g<<A[1]<<"\n";}
 return 0;
}