Cod sursa(job #2768359)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 10 august 2021 13:30:52
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <bits/stdc++.h>

using namespace std;

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

const int maxN = (int)1e5 + 5;

struct Node {
  int pref, suf, ans, l, r;
  Node(int _pref, int _suf, int _ans, int _l, int _r) {
    pref = _pref;
    suf = _suf;
    ans = _ans;
    l = _l;
    r = _r;
  }
  Node() {}
};

int n, q;

Node tree[4 * maxN];

int add[4 * maxN];

bool mark[4 * maxN];

Node combine(Node a, Node b) {
  Node ans;
  ans.ans = max(a.ans, b.ans);
  if (a.suf > 0 && b.pref > 0) {
    ans.ans = max(ans.ans, a.suf + b.pref);
  }
  if (a.r - a.l + 1 == a.pref) {
    ans.pref = a.pref + b.pref;
  } else {
    ans.pref = a.pref;
  }
  if (b.r - b.l + 1 == b.suf) {
    ans.suf = b.suf + a.suf;
  } else {
    ans.suf = b.suf;
  }
  ans.l = a.l;
  ans.r = b.r;
  return ans;
}

void push(int u, int l, int r) {
  if (mark[u]) {
    tree[u].ans = tree[u].pref = tree[u].suf = (r - l + 1) * add[u];
    if (l != r) {
      add[2 * u] = add[2 * u + 1] = add[u];
      mark[2 * u] = mark[2 * u + 1] = true;
    }
    mark[u] = false;
  }
}

void build(int u, int l, int r) {
  if (l == r) {
    tree[u] = Node(1, 1, 1, l, l);
    return;
  }
  int m = (l + r) / 2;
  build(2 * u, l, m);
  build(2 * u + 1, m + 1, r);
  tree[u] = combine(tree[2 * u], tree[2 * u + 1]);
}

void update(int u, int l, int r, int ql, int qr, int tp) {
  push(u, l, r);
  if (l > qr || r < ql) {
    return;
  }
  if (ql <= l && r <= qr) {
    tree[u].ans = tree[u].pref = tree[u].suf = (r - l + 1) * tp;
    if (l != r) {
      add[2 * u] = add[2 * u + 1] = tp;
      mark[2 * u] = mark[2 * u + 1] = true;
    }
    return;
  }
  int m = (l + r) / 2;
  update(2 * u, l, m, ql, qr, tp);
  update(2 * u + 1, m + 1, r, ql, qr, tp);
  tree[u] = combine(tree[2 * u], tree[2 * u + 1]);
}

int query(int u, int l, int r, int pos) {
  push(u, l, r);
  if (l == r) {
    return tree[u].ans;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    return query(2 * u, l, m, pos);
  }
  return query(2 * u + 1, m + 1, r, pos);
}

int main() {
  ios_base::sync_with_stdio(false);
  in.tie(NULL);
  out.tie(NULL);
  in >> n >> q;
  build(1, 1, n);
  for (int i = 1; i <= q; i++) {
    int op;
    in >> op;
    if (op == 3) {
      out << tree[1].ans << "\n";
    } else {
      int x, y;
      in >> x >> y;
      int tp = 1; // vin turisti - 0
      // pleaca - 1
      if (op == 1) {
        tp = 0;
      }
      update(1, 1, n, x, x + y - 1, tp);
    }
   // for (int j = 1; j <= n; j++) {
     // cout << query(1, 1, n, j) << " ";
  //  }
   // cout << "\n";
  }
  return 0;
}