Submission #850901

#	Time	Username	Problem	Language	Result	Execution time	Memory
850901		tvladm2009	Growing Trees (BOI11_grow)	C++17	0 / 100	132 ms	7000 KiB

grow

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int INF = (int) 2e9;
int a[N], tree[4 * N], lazy[4 * N];
int n, q;

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

/// freopen("input.txt", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  a[n + 1] = INF;
  n++;
  function<void(int, int, int)> build = [&](int v, int tl, int tr) {
    if (tl == tr) {
      tree[v] = a[tl];
      return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  };
  build(1, 1, n);
  function<void(int, int, int)> push = [&](int v, int tl, int tr) {
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    tree[v] += lazy[v];
    lazy[v] = 0;
  };
  function<void(int, int, int, int, int)> apply = [&](int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
      lazy[v]++;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    if (l <= tm) {
      apply(2 * v, tl, tm, l, min(tm, r));
    }
    if (tm + 1 <= r) {
      apply(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    }
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  };
  function<int(int, int, int, int)> smaller = [&](int v, int tl, int tr, int val) {
    push(v, tl, tr);
    if (tl == tr) {
      return tl;
    }
    int tm = (tl + tr) / 2;
    if (tree[2 * v] >= val) {
      return smaller(2 * v, tl, tm, val);
    }
    return smaller(2 * v + 1, tm + 1, tr, val);
  };
  function<int(int, int, int, int)> bigger = [&](int v, int tl, int tr, int val) {
    push(v, tl, tr);
    if (tl == tr) {
      return tl;
    }
    int tm = (tl + tr) / 2;
    if (tree[2 * v] > val) {
      return bigger(2 * v, tl, tm, val);
    }
    return bigger(2 * v + 1, tm + 1, tr, val);
  };
  function<int(int, int, int, int)> get_val = [&](int v, int tl, int tr, int pos) {
    push(v, tl, tr);
    if (tl == tr) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
      return get_val(2 * v, tl, tm, pos);
    }
    return get_val(2 * v + 1, tm + 1, tr, pos);
  };
  for (int iq = 1; iq <= q; iq++) {
    char type;
    int x, y;
    cin >> type >> x >> y;
    if (type == 'F') {
      int first = smaller(1, 1, n, y);
      if (first == n) {
        continue;
      }
      int last = first + x - 1;
      if (last >= n) {
        apply(1, 1, n, first, n - 1);
        continue;
      }
      int val = get_val(1, 1, n, last);
      int last_to_update = smaller(1, 1, n, val) - 1;
      if (first <= last_to_update) {
        apply(1, 1, n, first, last_to_update);
      }
      int rem = last - last_to_update;
      if (rem == 0) {
        continue;
      }
      last_to_update = bigger(1, 1, n, val) - 1;
      apply(1, 1, n, last_to_update - rem + 1, last_to_update);
    } else {
      cout << bigger(1, 1, n, y) - smaller(1, 1, n, x) << "\n";
    }
  }
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10