Cod sursa(job #2454521)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 8 septembrie 2019 20:15:15
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100000 + 7;
int p[4 * N];
int s[4 * N];
int t[4 * N];
int w[4 * N];

void push(int v, int len) {
  if (w[v]) {
    if (len > 1) {
      w[2 * v] = w[2 * v + 1] = w[v];
    }
    if (w[v] == 1) {
      p[v] = s[v] = t[v] = 0;
    } else {
      p[v] = s[v] = t[v] = len;
    }
    w[v] = 0;
  }
}

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



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

  int n, q;
  scanf("%d %d", &n, &q);
  upd(1, 1, n, 1, n, 2);
  for (int i = 1; i <= q; i++) {
    int tp;
    scanf("%d", &tp);
    if (tp <= 2) {
      int i, j;
      scanf("%d %d", &i, &j);
      upd(1, 1, n, i, i + j - 1, tp);
    } else {
      printf("%d\n", t[1]);
    }
  }

  return 0;
}