Cod sursa(job #2201076)

Utilizator bebeetarepredescu bebeetare Data 3 mai 2018 15:18:46
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("hotel.in");
ofstream g("hotel.out");
int n,q,tip,l,r;
struct smecherie
{
    int st,dr,sol,lazy;
}arb[100001*4];
void init(int nod,int a,int b)
{
    arb[nod].st=arb[nod].dr=arb[nod].sol=b-a+1;
    if(a==b)return;
    int mij=(a+b)/2;
    init(nod*2,a,mij);
    init(nod*2+1,mij+1,b);
}
void propag(int nod,int a,int b)
{
    if(arb[nod].lazy==0)return;
    if(arb[nod].lazy==1)
    {
        arb[nod].st=arb[nod].dr=arb[nod].sol=0;
    }
    else
    {
        arb[nod].st=arb[nod].dr=arb[nod].sol=b-a+1;
    }
    if(a<b)arb[2*nod].lazy=arb[2*nod+1].lazy=arb[nod].lazy;
    arb[nod].lazy=0;
}
void update(int nod,int a,int b,int ua,int ub,int val)
{
    int mij=(a+b)/2;
    if(ua<=a && b<=ub)
    {
        arb[nod].lazy=val;
        propag(nod,a,b);
        return;
    }
    propag(nod,a,b);
    if(ua<=mij)update(nod*2,a,mij,ua,ub,val);
    else propag(nod*2,a,mij);
    if(ub>mij)update(nod*2+1,mij+1,b,ua,ub,val);
    else propag(nod*2+1,mij+1,b);
    arb[nod].sol=max(arb[2*nod].dr+arb[2*nod+1].st,max(arb[2*nod].sol,arb[2*nod+1].sol));
    arb[nod].st=arb[2*nod].st;
    if(arb[nod].st==mij-a+1)arb[nod].st+=arb[2*nod+1].st;
    arb[nod].dr=arb[2*nod+1].dr;
    if(arb[nod].dr==b-mij)arb[nod].dr+=arb[2*nod].dr;
}
int main()
{
    f>>n>>q;
    init(1,1,n);
    for(int i=1;i<=q;i++)
    {
        f>>tip;
        if(tip==3)
        {
            propag(1,1,n);
            g<<arb[1].sol<<'\n';
        }
        else
        {
            f>>l>>r;
            r+=l-1;
            update(1,1,n,l,r,tip);
        }
    }
    return 0;
}