Cod sursa(job #2454520)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 8 septembrie 2019 20:11:40
Problema Hotel Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <cstdio>

using namespace std;

struct Node {
  int l;
  int t;
  int p;
  int s;
};

Node uni(Node a, Node b) {
  int l = a.l + b.l;
  int t = max(a.s + b.p, max(a.t, b.t));
  int p = a.p + (a.p == a.l) * b.p;
  int s = b.s + (b.s == b.l) * a.s;
  return {l, t, p, s};
}

const int N = (int) 1e5 + 7;
int n, q;
Node t[4 * N];
int w[4 * N];

void push(int v, int tl, int tr) {
  if (w[v]) {
    if (tl < tr) {
      w[2 * v] = w[2 * v + 1] = w[v];
    }
    if (w[v] == 1) {
      t[v] = {tr - tl + 1, 0, 0, 0};
    } else {
      t[v] = {tr - tl + 1, tr - tl + 1, tr - tl + 1, tr - tl + 1};
    }
    w[v] = 0;
  }
}

void upd(int v, int tl, int tr, int l, int r, int x) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    w[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  upd(2 * v, tl, tm, l, r, x);
  upd(2 * v + 1, tm + 1, tr, l, r, x);
  t[v] = uni(t[2 * v], t[2 * v + 1]);
}

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

  cin >> n >> q;
  upd(1, 1, n, 1, n, 2);
  while (q--) {
    int tp;
    cin >> tp;
    if (tp <= 2) {
      int i, j;
      cin >> i >> j;
      j = i + j - 1;
      upd(1, 1, n, i, j, tp);
    } else {
      cout << t[1].t << '\n';
    }
  }

  return 0;
}