Cod sursa(job #3138461)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 19 iunie 2023 18:12:19
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.14 kb
#include <bits/stdc++.h>

using namespace std;

const int inf = INT_MAX;

int n, p;

struct node
{
    int left, right, sum, len;
};

class LazySegTree
{
    vector <node> t;

    node mergeNodes(const node &x, const node &y)
    {
        node ans;
        ans.sum = max(max(x.right + y.left, x.sum), y.sum);
        ans.len = x.len + y.len;
        ans.right = y.right;
        if(y.len == y.sum)
            ans.right = y.sum + x.right;
        ans.left = x.left;
        if(x.len == x.sum)
            ans.left = x.sum + y.left;
        return ans;
    }

    void push(int v)
    {
        if(t[v].sum == 0  &&  t[2 * v].sum)
        {
            t[2 * v].left = 0;
            t[2 * v].right = 0;
            t[2 * v].sum = 0;

            t[2 * v + 1].left = 0;
            t[2 * v + 1].right = 0;
            t[2 * v + 1].sum = 0;
        }
        else if(t[v].sum  &&  t[2 * v].sum == 0)
        {
            t[2 * v].left = t[2 * v].len;
            t[2 * v].right = t[2 * v].len;
            t[2 * v].sum = t[2 * v].len;

            t[2 * v + 1].left = t[2 * v + 1].len;
            t[2 * v + 1].right = t[2 * v + 1].len;
            t[2 * v + 1].sum = t[2 * v + 1].len;
        }

    }

public:
    LazySegTree (int n)
    {
        t.resize(4 * n + 1);
    }

    void build(int v, int l, int r)
    {
        if(l == r)
        {
            t[v].left = 1;
            t[v].right = 1;
            t[v].sum = 1;
            t[v].len = 1;
            return;
        }

        int m = (l + r)/ 2;
        build(2 * v, l, m);
        build(2 * v + 1, m + 1, r);
        t[v] = mergeNodes(t[2 * v], t[2 * v + 1]);
    }

    void update(int v, int l, int r, int tl, int tr, int val)
    {
        if(tl > tr)
            return;
        if(l == tl  &&  r == tr)
        {
//            cout << l << " " << r << "\n";
            if(val == 0)
            {
                t[v].left = 0;
                t[v].right = 0;
                t[v].sum = 0;
                t[v].len = r - l + 1;
            }
            else
            {
                t[v].left = r - l + 1;
                t[v].right = r - l + 1;
                t[v].sum = r - l + 1;
                t[v].len = r - l + 1;
            }
        }
        else
        {
            push(v);
            int m = (l + r) / 2;
            update(2 * v, l, m, tl, min(m, tr), val);
            update(2 * v + 1, m + 1, r, max(tl, m + 1), tr, val);
            t[v] = mergeNodes(t[2 * v], t[2 * v + 1]);
        }
    }

    void print(int v, int l, int r)
    {
        if(l == r)
        {
            cout << l << " " << r << " " << t[v].left << " " << t[v].right << " " << t[v].sum << " " << t[v].len << " " << "\n";
            return;
        }

        int m = (l + r)/ 2;
        print(2 * v, l, m);
        print(2 * v + 1, m + 1, r);
        t[v] = mergeNodes(t[2 * v], t[2 * v + 1]);
        cout << l << " " << r << " " << t[v].left << " " << t[v].right << " " << t[v].sum << " " << t[v].len << " " << "\n";

    }

    node query(int v, int l, int r, int tl, int tr)
    {
        if(tl > tr)
            return {0, 0, 0, 0};
        if(l == tl  &&  r == tr)
            return t[v];

        push(v);
        int m = (l + r) / 2;
        return mergeNodes(query(2 * v, l, m, tl, min(m, tr)),
                          query(2 * v + 1, m + 1, r, max(m + 1, tl), tr));
    }

};

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);

    cin >> n >> p;

    LazySegTree aint(n);
    aint.build(1, 1, n);
    for(int i = 1; i <= p; i ++)
    {
        int c;
        cin >> c;
        if(c == 3)
            cout << aint.query(1, 1, n, 1, n).sum << "\n";
        else
        {
            int poz, len;
            cin >> poz >> len;
            if(c == 1)
                aint.update(1, 1, n, poz, poz + len - 1, 0);
            else
                aint.update(1, 1, n, poz, poz + len - 1, 1);
//            aint.print(1, 1, n);
//            cout << "\n";
        }
    }
    return 0;
}