Cod sursa(job #1297332)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 21 decembrie 2014 22:08:38
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#define DIM 100002
using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");
struct hotel{int l,r,s;}a[4*DIM];
int n,i,j,op,q;
void build(int nod,int p,int u){
    if(p==u){
        a[nod].s=a[nod].r=a[nod].l=1;
        return;
    }
    int mid=(p+u)/2;
    build(2*nod,p,mid);
    build(2*nod+1,mid+1,u);
    a[nod].l=a[nod].r=a[nod].s=a[2*nod].s+a[2*nod+1].s;
}
void update(int nod,int p,int u,int A,int B,int val){
    if(p>=A && u<=B){
        if(val==1)
            a[nod].s=a[nod].l=a[nod].r=0;
        else
            a[nod].s=a[nod].l=a[nod].r=u-p+1;
        return;
    }
    int mid=(p+u)/2;
    if(a[nod].s==0){
        a[2*nod].s=a[2*nod].l=a[2*nod].r=0;
        a[2*nod+1].s=a[2*nod+1].l=a[2*nod+1].r=0;
    }
    if(a[nod].s==u-p+1){
        a[2*nod].s=a[2*nod].l=a[2*nod].r=mid-p+1;
        a[2*nod+1].s=a[2*nod+1].l=a[2*nod+1].r=u-mid;
    }
    if(A<=mid)
        update(2*nod,p,mid,A,B,val);
    if(B>mid)
        update(2*nod+1,mid+1,u,A,B,val);
    a[nod].s=max(a[2*nod].r+a[2*nod+1].l,max(a[2*nod].s,a[2*nod+1].s));
    a[nod].l=a[2*nod].l;
    a[nod].r=a[2*nod+1].r;
    if(a[2*nod].l==mid-p+1)
        a[nod].l+=a[2*nod+1].l;
    if(a[2*nod+1].r==u-mid)
        a[nod].r+=a[2*nod].r;

}
int main(){
    fin>>n>>q;
    build(1,1,n);
    while(q--){
        fin>>op;
        if(op==1){
            fin>>i>>j;
            update(1,1,n,i,i+j-1,1);
            continue;
        }
        if(op==2){
            fin>>i>>j;
            update(1,1,n,i,i+j-1,0);
            continue;
        }
        fout<<a[1].s<<'\n';
    }
    fin.close();fout.close();
    return 0;
}