Cod sursa(job #2918075)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 9 august 2022 18:00:11
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.34 kb
#include <fstream>
#include <vector>


using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");
const int MAXINTER = 131073;
const int MAXTSIZE = 2 * MAXINTER;

struct tip_tree
{
    int lung, pref, seg, suf, lazy;
};

vector <tip_tree>tree;
int init(int &intersize, int n)
{
    intersize = 1;
    while(intersize < n)
        intersize <<= 1;
    tree.resize(intersize << 1);
}

tip_tree comb(tip_tree a, tip_tree b, int node)
{
    int newseg = max(a.seg, max(b.seg, a.suf + b.pref));
    int newpref = a.pref;
    if(a.pref == a.lung)
        newpref = max(newpref, a.lung + b.pref);
    int newsuf = b.suf;
     if(b.suf == b.lung)
        newsuf = max(newsuf, b.lung + a.suf);
    int newlung = a.lung + b.lung;
    return {newlung, newpref, newseg, newsuf, tree[node].lazy};
}

void update(int l, int r, int val, int node, int lx, int rx)
{
    if(rx - lx != 1)
    {
        if(tree[node].lazy == -1)
        {
            tree[2 * node + 1] = {tree[2 * node + 1].lung,
            tree[2 * node + 1].lung, tree[2 * node + 1].lung,
            tree[2 * node + 1].lung, -1};

            tree[2 * node + 2] = {tree[2 * node + 2].lung,
            tree[2 * node + 2].lung, tree[2 * node + 2].lung,
            tree[2 * node + 2].lung, -1};
        }
        else if(tree[node].lazy == 1)
        {
            tree[2 * node + 1] = {tree[2 * node + 1].lung,
            0, 0, 0, 1};

            tree[2 * node + 2] = {tree[2 * node + 2].lung,
            0, 0, 0, 1};
        }
        tree[node].lazy = 0;
    }

    /// lung, pref, seg, suf, lazy
    if(l <= lx && rx <= r)
    {
        if(val == -1)
            tree[node] = {tree[node].lung, tree[node].lung, tree[node].lung, tree[node].lung, tree[node].lazy};
        else
            tree[node] = {tree[node].lung, 0, 0 , 0, tree[node].lazy};
        tree[node].lazy += val;
        return;
    }
    if(rx <= l || lx >= r)
        return;

    int mij = (lx + rx) / 2;
    if(mij >= l)
        update(l, r, val, 2 * node + 1, lx, mij);
    if(mij <= r)
        update(l, r, val, 2 * node + 2, mij, rx);
    tree[node] = comb(tree[2 * node + 1], tree[2 * node + 2], node);
}
void setare(int n, int i, int node, int lx, int rx)
{
    if(rx - lx == 1)
    {
        if(lx < n)/// lung, pref, seg, suf, lazy
            tree[node] = {1, 1, 1, 1, 0};
        else
            tree[node] = {0, 0, 0, 0, 0};
        return;
    }

    int mij = (lx + rx) / 2;
    if(mij > i)
        setare(n, i, 2 * node + 1, lx, mij);
    else
        setare(n, i, 2 * node + 2, mij, rx);
    tree[node] = comb(tree[2 * node + 1], tree[2 * node + 2], node);
}


int query()
{
    return tree[0].seg;
}


int main()
{
    int n, q, intersize = 1, i;

    fin >> n >> q;
    init(intersize, n);

    for(i = 0; i < intersize; i++)
        setare(n, i, 0, 0, intersize);


   for(i = 0; i < q; i++)
    {
        int tip, l, r, lung;
        fin >> tip;
        if(tip == 1)
        {
            fin >> l >> lung;
            l--;
            update(l, l + lung, 1, 0, 0, intersize);
        }
        else if(tip == 2)
        {
            fin >> l >> lung;
            l--;
            update(l, l + lung, -1, 0, 0, intersize);
        }
        else
            fout << query() << '\n';
    }


    return 0;
}