Cod sursa(job #1400749)

Utilizator ThomasFMI Suditu Thomas Thomas Data 25 martie 2015 13:46:28
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
using namespace std;

#define NMax 100005
#define AMax 400005

ifstream f("hotel.in");
ofstream g("hotel.out");

int n;
int AS[AMax],AM[AMax],AD[AMax];

void update(int nod,int st,int dr,int a,int b,int type)
{
    if(a <= st && dr <= b)
    {
        if(type == 2) AS[nod] = AM[nod] = AD[nod] = dr-st+1;
        else AS[nod] = AM[nod] = AD[nod] = 0;
        return;
    }

    int mij = ((st+dr)>>1);
    int fiu1 = (nod<<1);
    int fiu2 = ((nod<<1)|1);

    if(AM[nod] == 0)
    {
        AS[fiu1] = AM[fiu1] = AD[fiu1] = 0;
        AS[fiu2] = AM[fiu2] = AD[fiu2] = 0;
    }

    if(a <= mij) update(fiu1,st,mij,a,b,type);
    if(b > mij) update(fiu2,mij+1,dr,a,b,type);

    AS[nod] = AS[fiu1];
    if(AS[nod] == mij-st+1) AS[nod] += AS[fiu2];

    AD[nod] = AD[fiu2];
    if(AD[nod] == dr-mij) AD[nod] += AD[fiu1];

    AM[nod] = max(max(AM[fiu1],AM[fiu2]),AD[fiu1]+AS[fiu2]);
}

int main()
{
    int i,Q;

    f>>n>>Q;
    for(i=1;i<=n;++i) update(1,1,n,i,i,2);

    int t,x,y;

    while(Q--)
    {
        f>>t;
        if(t == 3) g<<AM[1]<<"\n";
        else
        {
            f>>x>>y;
            y = x+y-1;
            update(1,1,n,x,y,t);
        }
    }

    f.close();
    g.close();
    return 0;
}