Cod sursa(job #2407745)

Utilizator Constantin.Dragancea Constantin Constantin. Data 17 aprilie 2019 10:51:35
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define L (nod << 1)
#define R (L | 1)
#define smax(X, Y) ((X) > (Y) ? (X) : (Y))
int n, p, lazy[4*N];
struct lol{
    int st, dr, bst;
} h[4*N];

void push(int nod, int st, int dr){
    if (!lazy[nod]) return;
    if (lazy[nod] == 2){
        int nr = dr - st + 1;
        h[nod] = {nr, nr, nr};
        if (st != dr) lazy[L] = lazy[R] = lazy[nod];
        lazy[nod] = 0;
    }
    else{
        h[nod] = {0, 0, 0};
        if (st != dr) lazy[L] = lazy[R] = lazy[nod];
        lazy[nod] = 0;
    }
}

void update(int nod, int st, int dr, int l, int r, int c){
    if (st >= l && dr <= r){
        lazy[nod] = c;
        push(nod, st, dr);
        return;
    }
    push(nod, st, dr);
    int mid = (st + dr) >> 1;
    if (l <= mid) update(L, st, mid, l, r, c);
    else push(L, st, mid);
    if (r > mid) update(R, mid+1, dr, l, r, c);
    else push(R, mid+1, dr);
    if (h[L].st == mid - st + 1) h[nod].st = h[L].st + h[R].st;
    else h[nod].st = h[L].st;
    if (h[R].dr == dr - mid) h[nod].dr = h[R].dr + h[L].dr;
    else h[nod].dr = h[R].dr;
    h[nod].bst = smax(smax(h[L].bst, h[R].bst), h[L].dr + h[R].st);
}

int main(){
    ios_base::sync_with_stdio(0);
    ifstream cin ("hotel.in");
    ofstream cout ("hotel.out");
    cin >> n >> p;
    update(1, 1, n, 1, n, 2);
    while (p--){
        int c, a, b;
        cin >> c;
        if (c == 3) cout << h[1].bst << '\n';
        else cin >> a >> b, update(1, 1, n, a, a+b-1, c);
    }
    return 0;
}