Cod sursa(job #2851585)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 18 februarie 2022 20:36:35
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
 // #include <iostream>
#include <vector>

using namespace std;

ifstream cin ("hotel.in");
ofstream cout ("hotel.out");

struct seg {
    int left, right, max;
    int add;
};

int n;

struct Aint {
    int size = 1;
    vector<seg> aint;
    void init (int n)
    {
        while (size <= n)
            size *= 2;
        aint.resize(size * 2 + 1);
    }
    
    void build (int pos, int l, int r)
    {
    //    cout << pos << ' '  << l << ' ' << r << '\n';
        aint[pos].left = aint[pos].max = aint[pos].right = r - l + 1;
    
        if (l < r)
        {
            int m = (l + r) / 2;
            build (pos * 2, l, m);
            build (pos * 2 + 1, m + 1, r);
        }
    }

    void buildAint ()
    {
        build(1, 1, n);
    }

    void lazy (int pos, int s, int d, int l, int r, int val)
    {
    
        if (l > d || r < s) {
            return;
        }
        else if (s <= l && r <= d)
        {
            aint[pos].add += val;            
        /*    if (aint[pos].add == 0)
            {
                aint[pos].left = aint[pos].right = aint[pos].max = r - l + 1;
            }
            else {
                aint[pos].left = aint[pos].right = aint[pos].max = 0;
            }*/
        }
        else {
            aint[pos * 2].add += aint[pos].add;
            aint[pos * 2 + 1].add += aint[pos].add;
            aint[pos].add = 0;

            int m = (l + r) / 2;
            lazy(pos * 2, s, d, l, m, val);
            lazy(pos * 2 + 1, s, d, m + 1, r, val);
            
            aint[pos].left = aint[pos * 2].left * (aint[pos * 2].add == 0);
            if (aint[pos].left == m - l + 1 && aint[pos * 2 + 1].add == 0)
                aint[pos].left += aint[pos * 2 + 1].left;

            aint[pos].right = aint[pos * 2 + 1].right * (aint[pos * 2 + 1].add == 0);
            if (aint[pos].right == r - m && aint[pos * 2].add == 0)
                aint[pos].right += aint[pos * 2].right;
            
            aint[pos].max = max (aint[pos * 2].max * (aint[pos * 2].add == 0),
             aint[pos * 2 + 1].max * (aint[pos * 2 + 1].add == 0));
            aint[pos].max = max (aint[pos].max, aint[pos * 2].right * (aint[pos * 2].add == 0)
             + aint[pos * 2 + 1].left * (aint[pos * 2 + 1].add == 0));
        //    cout << pos << ' ' << l << ' ' << r << ' ' << aint[pos].max << '\n';
        }
    }

    void lazyUpdate (int s, int d, int val)
    {
        lazy(1, s, d, 1, n, val);
    }


};

int main ()
{
    int q, c;
    int s, m;
    cin >> n >> q;
    struct Aint aint;
    aint.init(n);
    aint.buildAint();
    while (q--)
    {
        cin >> c;
        if (c == 3)
        {
            cout << aint.aint[1].max << '\n';
        }
        else if (c == 1)
        {
            cin >> s >> m;
            aint.lazyUpdate(s, s + m - 1, 1);
        }
        else {
            cin >> s >> m;
            aint.lazyUpdate(s, s + m - 1, -1);
        }
    }
}