Cod sursa(job #1292335)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 14 decembrie 2014 09:43:23
Problema Hotel Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#define MAXN 100000
#define LOGN 17
#define MAXP (1<<(LOGN+1))
int lmax[MAXP], left[MAXP], right[MAXP];
char mark[MAXP];
int a, b, t;
inline int max2(int x, int y){
    if(x>=y){
        return x;
    }
    return y;
}
inline int max3(int x, int y, int z){
    return max2(max2(x, y), z);
}
void update(int p, int st, int dr){
    int m=(st+dr)/2;
    if((a<=st)&&(dr<=b)){
        lmax[p]=left[p]=right[p]=t*(dr-st+1);
        mark[p]=1;
        return ;
    }
    if(mark[p]==1){
        lmax[2*p+1]=left[2*p+1]=right[2*p+1]=(lmax[p]!=0)*(m-st+1);
        lmax[2*p+2]=left[2*p+2]=right[2*p+2]=(lmax[p]!=0)*(dr-m);
        mark[2*p+1]=mark[2*p+2]=1;
        mark[p]=0;
    }
    if(a<=m){
        update(2*p+1, st, m);
    }
    if(b>m){
        update(2*p+2, m+1, dr);
    }
    left[p]=left[2*p+1];
    if(left[2*p+1]==m-st+1){
        left[p]+=left[2*p+2];
    }
    right[p]=right[2*p+2];
    if(right[2*p+2]==dr-m){
        right[p]+=right[2*p+1];
    }
    lmax[p]=max3(lmax[2*p+1], lmax[2*p+2], right[2*p+1]+left[2*p+2]);
}
void dfs(int p, int st, int dr){
    int m=(st+dr)/2;
    lmax[p]=left[p]=right[p]=dr-st+1;
    if(st==dr){
        return ;
    }
    dfs(2*p+1, st, m);
    dfs(2*p+2, m+1, dr);
}
int main(){
    int n, q, i;
    FILE *fin, *fout;
    fin=fopen("hotel.in", "r");
    fout=fopen("hotel.out", "w");
    fscanf(fin, "%d%d", &n, &q);
    dfs(0, 0, n-1);
    for(i=0; i<q; i++){
        fscanf(fin, "%d", &t);
        if(t==3){
            fprintf(fout, "%d\n", lmax[0]);
        }else{
            fscanf(fin, "%d%d", &a, &b);
            b+=a-1;
            a--;
            b--;
            t--;
            update(0, 0, n-1);
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}