Cod sursa(job #1889650)

Utilizator tqmiSzasz Tamas tqmi Data 22 februarie 2017 20:20:36
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#define Nmax 300000
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");

struct Adi
{
    int max_l,max_ll,max_lr,sum;
};

Adi AI[Nmax];
int N,P;
void Build(int Nod,int L,int R)
{
    int mid=(L+R)/2;
    if(L==R)
    {
        AI[Nod].max_l=1;
        AI[Nod].max_ll=1;
        AI[Nod].max_lr=1;
        AI[Nod].sum=1;
        return;
    }
    int son1=Nod*2,son2=Nod*2+1;
    Build(son1,L,mid);
    Build(son2,mid+1,R);
    AI[Nod].max_l=AI[son1].max_l+AI[son2].max_l;
    AI[Nod].max_ll=AI[Nod].max_l;
    AI[Nod].max_lr=AI[Nod].max_l;
    AI[Nod].sum=AI[Nod].max_l;
}

void Up1(int Nod,int L,int R,int lm,int rm,int val)
{
    int mid=(L+R)/2;
    if(L==R)
    {
        AI[Nod].max_l=val;
        AI[Nod].max_ll=val;
        AI[Nod].max_lr=val;
        return;
    }
    int son1=Nod*2,son2=Nod*2+1;
    if(lm<=mid)
        Up1(son1,L,mid,lm,rm,val);
    if(rm>mid)
        Up1(son2,mid+1,R,lm,rm,val);
    AI[Nod].max_l=max(AI[son1].max_l,AI[son2].max_l);
    if(AI[son1].max_ll==AI[son1].sum)
        AI[Nod].max_ll=AI[son1].max_ll+AI[son2].max_ll;
    else
        AI[Nod].max_ll=AI[son1].max_ll;
    if(AI[son2].max_lr==AI[son2].sum)
        AI[Nod].max_lr=AI[son2].max_lr+AI[son1].max_lr;
    else
        AI[Nod].max_lr=AI[son2].max_lr;
    AI[Nod].max_l=max(AI[Nod].max_l,max(AI[Nod].max_lr,max(AI[Nod].max_ll,AI[son1].max_lr+AI[son2].max_ll)));
}


int main()
{
    fin>>N>>P;
    Build(1,1,N);
    for(int i=1;i<=P;i++)
    {
        int c,x,y;
        fin>>c;
        switch(c)
        {
        case 1:
            fin>>x>>y;
            Up1(1,1,N,x,x+y-1,0);
            break;
        case 2:
            fin>>x>>y;
            Up1(1,1,N,x,x+y-1,1);
            break;
        case 3:
            fout<<AI[1].max_l<<"\n";
            break;
        }
    }
    return 0;
}