Cod sursa(job #3135478)

Utilizator AnastasiaStefanescuAnastasia Stefanescu AnastasiaStefanescu Data 3 iunie 2023 13:48:30
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <fstream>
using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");

int arb[800005], v[800005], n, m, poz_crt;
struct node{
    int prefix, sufix, submax, sumtot, lazy;
}info[800005];

node combina_info_din_doua_noduri(node nod1, node nod2, node nod) //nodurile trb sa fie vecine!!
{
    if(nod1.prefix == nod1.sumtot)
        nod.prefix = nod1.sumtot + nod2.prefix;
    else
        nod.prefix = nod1.prefix;
    
    if(nod2.sufix = nod2.sumtot)
        nod.sufix = nod2.sumtot + nod1.sufix;
    else
        nod.sufix = nod2.sufix;
    
    nod.sumtot = nod1.sumtot + nod2.sumtot;
    nod.submax = max(max(nod1.submax, nod2.submax), nod2.prefix + nod1.sufix);
    //nod.lazy = 0;
    return nod;
                      
}

void build(int nr_nod, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        arb[nr_nod] = val;
        if(val > 0)
            info[nr_nod].submax = info[nr_nod].prefix = info[nr_nod].sufix = info[nr_nod].sumtot = val;
        
        else
        {
            info[nr_nod].submax = info[nr_nod].prefix = info[nr_nod].sufix = 0;
            info[nr_nod].sumtot = val;
        }
        return;
    }
    if(st<dr)
    {
        int mij = (st+dr)/2;
        build(nr_nod*2, st, mij, poz, val);
        build(nr_nod*2+1, mij+1, dr, poz, val);
        info[nr_nod] = combina_info_din_doua_noduri(info[nr_nod*2], info[nr_nod*2+1], info[nr_nod]);
    }
    info[nr_nod].lazy = 0;
}

void update_nod(int nr_nod, int st, int dr)
{
    
    if(info[nr_nod].lazy == 1)
        info[nr_nod].prefix = info[nr_nod].sufix = info[nr_nod].sumtot = info[nr_nod].submax =  dr - st + 1;
    else
        if(info[nr_nod].lazy == -1)
            info[nr_nod].prefix = info[nr_nod].sufix = info[nr_nod].sumtot = info[nr_nod].submax =  0;
    
    if(st != dr && info[nr_nod].lazy != 0)
    {
        info[2*nr_nod].lazy = info[2*nr_nod+1].lazy = info[nr_nod].lazy;
        info[nr_nod].lazy = 0;
    }
    
}

void update(int nod, int st, int dr, int a, int b, int val)
{
    
    if(a >dr || b < st || st > dr)
        return;
    if(a<=st && dr<=b)
    {
        info[nod].lazy = val;
    }
    else
    {
        if(info[nod].lazy != 0)
            update_nod(nod, st, dr);
        int mij = (st + dr)/2;
        update(nod*2, st, mij, a, b, val);
        update(nod*2+1, mij+1, dr, a, b, val);
        update_nod(nod*2, st, mij);
        update_nod(nod*2+1, mij+1, dr);
        info[nod] = combina_info_din_doua_noduri(info[nod*2], info[nod*2+1], info[nod]);
    }
}

node query(int nod, int st, int dr, int a, int b)
{
    if(a<= st && dr<= b)
        return info[nod];
    int mij  = (st+dr)/2;
    node sub_st = {0,0,0,0}, sub_dr = {0, 0, 0,0}, rez = {0, 0, 0,0};
    sub_st = query(nod*2, st, mij, a, b);
    sub_dr = query(nod*2+1, mij+1, dr, a, b);
    rez = combina_info_din_doua_noduri(sub_st, sub_dr, rez);
    return rez;
}

int main()
{
    int i, tip, a, b, val;
    fin >> n >> m;
    
    for(i = 1; i<= n; i++)
        build(1, 1, n, i, 1);
    
    for (i = 1; i<= m; i++)
    {
        fin >> tip;
        if(tip == 3)
            fout << query(1, 1, n, 1, n).submax << '\n';
        else
        {
            fin >> a >> b;
            if(tip == 2)
            {
                update(1,1,n,a, a+b-1, 1);
            }
            else
            {
                update(1,1,n,a, a+b-1, -1);
            }
        }
    }
}