Cod sursa(job #979649)

Utilizator andrettiAndretti Naiden andretti Data 2 august 2013 11:37:38
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<stdio.h>
#include<algorithm>
#define maxait 1<<20
using namespace std;

struct seg_tree{int st,dr,maxx,lazy;} ait[maxait];
int n,p;

void build(int k,int left,int right)
{
    ait[k].st=ait[k].dr=ait[k].maxx=right-left+1;
    if(left==right) return;
    int mid=(left+right)>>1;
    build(2*k,left,mid);
    build(2*k+1,mid+1,right);
}

void single_update(int k,int left,int right,int type)
{
    if(type==1) ait[k].st=ait[k].dr=ait[k].maxx=0;
    else ait[k].st=ait[k].dr=ait[k].maxx=right-left+1;

    ait[k].lazy=0;
    if(left==right) return;
    ait[2*k].lazy=ait[2*k+1].lazy=type;
}

void lazy_update(int k,int left,int right,int x,int y,int type)
{
    if( x<=left && right<=y ) {single_update(k,left,right,type); return;}

    if(ait[k].lazy) single_update(k,left,right,ait[k].lazy);
    int mid=(left+right)/2;
    if(x<=mid) lazy_update(2*k,left,mid,x,y,type);
    if(y>mid) lazy_update(2*k+1,mid+1,right,x,y,type);

    if(ait[2*k].lazy) single_update(2*k,left,mid,ait[2*k].lazy);
    if(ait[2*k+1].lazy) single_update(2*k+1,mid+1,right,ait[2*k+1].lazy);

    ait[k].st=ait[2*k].st;
    if(ait[2*k].st==mid-left+1) ait[k].st+=ait[2*k+1].st;

    ait[k].dr=ait[2*k+1].dr;
    if(ait[2*k+1].dr==right-mid) ait[k].dr+=ait[2*k].dr;

    ait[k].maxx=max(max(ait[2*k].maxx,ait[2*k+1].maxx),ait[2*k].dr+ait[2*k+1].st);
}

void solve()
{
    int type,x,y;

    scanf("%d%d",&n,&p);
    build(1,1,n);
    for(int i=1;i<=p;i++)
    {
        scanf("%d",&type);
        if(type==3) {printf("%d\n",ait[1].maxx); continue;}
        scanf("%d%d",&x,&y);
        if(type==1) lazy_update(1,1,n,x,x+y-1,1);
        else lazy_update(1,1,n,x,x+y-1,2);
    }
}

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

    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}