Cod sursa(job #3152655)

Utilizator IanisBelu Ianis Ianis Data 26 septembrie 2023 09:58:24
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define lsb(x) (x & (-x))

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
#define FILE_NAME "hotel"
ifstream fin(FILE_NAME ".in");
ofstream fout(FILE_NAME ".out");
#define endl '\n'
#endif

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 1e5+5;
const int INF = 1e9+5;

struct Node {
    int mxl, mxr, mx;
    int lazy;
};

int n, m;
Node aint[4 * NMAX];

void aint_build(int node, int l, int r) {
    if (l >= r) {
        aint[node].mxl = aint[node].mxr = aint[node].mx = 1;
        return;
    }

    int mid = (l + r) >> 1;

    aint_build(node * 2, l, mid);
    aint_build(node * 2 + 1, mid + 1, r);

    aint[node].mxl = aint[node].mxr = aint[node].mx = r - l + 1;
}

void aint_propag(int node, int l, int r) {
    if (aint[node].lazy == 0) return;

    int mid = (l + r) >> 1;

    aint[node].mx = aint[node].mxl = aint[node].mxr = aint[node].lazy == 1 ? (r - l + 1) : 0;

    if (l < r) {
        aint[node * 2].lazy = aint[node].lazy;
        aint[node * 2 + 1].lazy = aint[node].lazy;
    }

    aint[node].lazy = 0;
}

void aint_comb(int node, int l, int r) {
    int mid = (l + r) >> 1;

    aint[node].mx = max(aint[node * 2].mx, aint[node * 2 + 1].mx);
    aint[node].mx = max(aint[node].mx, aint[node * 2].mxr + aint[node * 2 + 1].mxl);

    aint[node].mxl = aint[node * 2].mxl;
    aint[node].mxr = aint[node * 2 + 1].mxr;

    if (aint[node].mxl == mid - l + 1) aint[node].mxl += aint[node * 2 + 1].mxl;
    if (aint[node].mxr == r - mid) aint[node].mxr += aint[node * 2].mxr;
}

void aint_update(int node, int l, int r, int ll, int rr, int val) {
    aint_propag(node, l, r);

    if (ll <= l && r <= rr) {
        aint[node].lazy -= val;
        aint_propag(node, l, r);
        return;
    }

    int mid = (l + r) >> 1;

    if (ll <= mid) aint_update(node * 2, l, mid, ll, rr, val);
    else aint_propag(node * 2, l, mid);
    if (mid < rr) aint_update(node * 2 + 1, mid + 1, r, ll, rr, val);
    else aint_propag(node * 2 + 1, mid + 1, r);

    aint_comb(node, l, r);
}

int aint_query() {
    aint_propag(1, 1, n);
    return aint[1].mx;
}

/*
0 0 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 1 1 0
0 0 1 1 1 0 1 1 0 1 1 0

0 1 1 0 0 0 0 0 0 0 0 0
*/

signed main() {
    fin >> n >> m;

    aint_build(1, 1, n);

    while (m--) {
        int t, x, l;
        fin >> t;
        if (t == 1) {
            fin >> x >> l;
            aint_update(1, 1, n, x, x + l - 1, 1);
        } else if (t == 2) {
            fin >> x >> l;
            aint_update(1, 1, n, x, x + l - 1, -1);
        } else {
            fout << aint_query() << endl;
        }
    }

    return 0;
}