Cod sursa(job #1764148)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 25 septembrie 2016 00:58:51
Problema Hotel Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<cstdio>
#include <algorithm>
using namespace std;

const int N=100005;
struct nod{
    int s,st,dr,best,lazy;
} v[4*N];
int n;

void Compute(int pos, int x){
    if(v[pos].s==0){
        v[pos].st=x;
        v[pos].dr=x;
        v[pos].best=x;
    }
    else{
        v[pos].st=0;
        v[pos].dr=0;
        v[pos].best=0;
    }
}

void Union(int pos, int a, int b){
    if(v[2*pos].s==0 or v[2*pos].lazy!=0 or v[2*pos].s==a) Compute(2*pos, a);
    if(v[2*pos+1].s==0 or v[2*pos+1].lazy!=0 or v[2*pos+1].s==b) Compute(2*pos+1, b);

    v[pos].s=v[2*pos].s+v[2*pos+1].s;
    v[pos].st=v[2*pos].st;
    if(v[2*pos].s==0) v[pos].st=a+v[2*pos+1].st;
    v[pos].dr=v[2*pos+1].dr;
    if(v[2*pos+1].s==0) v[pos].dr=b+v[2*pos].dr;
    v[pos].best=max(max(v[2*pos].best, v[2*pos+1].best), v[2*pos].dr+v[2*pos+1].st);
}

void Update(int pos, int st, int dr, int a, int b, int val){
    if(st>b or dr<a) return;

    if(a<=st and dr<=b){
        int x=dr-st+1;
        v[pos].lazy+=val;
        v[pos].s+=x*val;
        if(st==dr){
            v[pos].lazy=0;
            return;
        }
    }

    v[2*pos].lazy+=v[pos].lazy;
    v[2*pos].s+=((st+dr)/2-st+1)*v[pos].lazy;
    v[2*pos+1].lazy+=v[pos].lazy;
    v[2*pos+1].s+=(dr-(st+dr)/2)*v[pos].lazy;
    v[pos].lazy=0;
    if(a<=st and dr<=b) return;

    Update(2*pos, st, (st+dr)/2, a, b, val);
    Update(2*pos+1, (st+dr)/2+1, dr, a, b, val);
    Union(pos, (st+dr)/2-st+1, dr-(st+dr)/2);
}

int main(){

    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);

    int m,i,t,a,b,dist;

    scanf("%d%d",&n,&m);
    v[1].best=n;
    for(i=1;i<=m;i++){
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d",&a,&dist);
            b=a+dist-1;
            Update(1,1,n,a,b,1);
        }
        if(t==2){
            scanf("%d%d",&a,&dist);
            b=a+dist-1;
            Update(1,1,n,a,b,-1);
        }
        if(t==3){
            printf("%d\n",v[1].best);
        }
    }

    return 0;
}