oj.uz

Submission #850901

# Submission time Handle Problem Language Result Execution time Memory
850901 2023-09-17T17:55:16 Z tvladm2009 Growing Trees (BOI11_grow) C++17
0 / 100
 132 ms 7000 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7000 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 5976 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 6904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 6744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 4904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7000 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 5728 KB Output isn't correct
2 Halted 0 ms 0 KB -