Cod sursa(job #3187007)

Utilizator ScipexRobert Chiri Scipex Data 26 decembrie 2023 21:55:43
Problema Hotel Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, t;

struct ArbInt {
    struct El {
        int lmax = 1;
        int lst = 1, lsf = 1;
        int lung = 1;
        int upd = 0;
    };
    vector<El> v;

    ArbInt(int n) : v(n * 4) {
    }

    void init(int st = 1, int dr = n, int idx = 1) {
        if (st == dr) {
            return;
        }

        int mij = (st + dr) / 2;
        // fout << st << " " << dr << " " << mij << endl;
        init(st, mij, idx * 2);
        init(mij + 1, dr, idx * 2 + 1);

        v[idx].lung = v[idx * 2].lung + v[idx * 2 + 1].lung;
        v[idx].lmax = v[idx].lung;
        v[idx].lst = v[idx].lung;
        v[idx].lsf = v[idx].lung;
    }

    void add(bool scot, int i, int j, int st = 1, int dr = n, int idx = 1) {
        if (i <= st && dr <= j) {
            v[idx].lmax = v[idx].lung * scot;
            v[idx].lst = v[idx].lung * scot;
            v[idx].lsf = v[idx].lung * scot;
        }
        if (st != dr) {
            int mij = (st + dr) / 2;
            if (i <= mij) {
                add(scot, i, j, st, mij, idx * 2);
            }
            if (j > mij) {
                add(scot, i, j, mij + 1, dr, idx * 2 + 1);
            }

            v[idx].lst = v[idx * 2].lst;
            if (v[idx * 2].lst == v[idx * 2].lung) {
                v[idx].lst += v[idx * 2 + 1].lst;
            }
            v[idx].lsf = v[idx * 2 + 1].lsf;
            if (v[idx * 2 + 1].lsf == v[idx * 2 + 1].lung) {
                v[idx].lsf += v[idx * 2].lsf;
            }
            v[idx].lmax =
                max(max(v[idx * 2].lmax, v[idx * 2 + 1].lmax), v[idx * 2].lsf + v[idx * 2 + 1].lst);
        }
    }
};

int main() {
    fin >> n >> m;
    ArbInt a(n);
    a.init();

    for (int i = 0; i < m; i++) {
        fin >> t;
        if (t == 3) {
            fout << a.v[1].lmax << endl;
        } else {
            fin >> x >> y;
            a.add(t - 1, x, x + y - 1);
        }
    }
}