Submission #225513

#	Time	Username	Problem	Language	Result	Execution time	Memory
225513		Haunted_Cpp	Growing Trees (BOI11_grow)	C++17	100 / 100	173 ms	6172 KiB

grow

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;

int a [N];

struct E {
  int mx, lazy;
  E () { mx = numeric_limits<int>::min() ;}
  E (int delta) {
    mx = delta;
    lazy = 0;
  }
  void merge (E l, E r) {
    mx = max (l.mx, r.mx);
  }
} seg[4 * N];

void build (int l, int r, int node) {
  if (l == r) {
    seg[node] = E(a[l]);
  } else {
    int mid = l + (r - l) / 2;
    build (l, mid, 2 * node + 1);
    build (mid + 1, r, 2 * node + 2);
    seg[node].merge (seg[2 * node + 1], seg[2 * node + 2]);
  }
}

void push (int l, int r, int node) {
  seg[node].mx += seg[node].lazy;
  if (l != r) {
    seg[2 * node + 1].lazy += seg[node].lazy;
    seg[2 * node + 2].lazy += seg[node].lazy;
  }
  seg[node].lazy = 0;
}

void range_update (int ql, int qr, int l, int r, int node, int delta) {
  if (seg[node].lazy != 0) push (l, r, node);
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    seg[node].lazy += delta;
    push (l, r, node);
  } else {
    int mid = l + (r - l) / 2;
    range_update (ql, qr, l, mid, 2 * node + 1, delta);
    range_update (ql, qr, mid + 1, r, 2 * node + 2, delta);
    seg[node].merge (seg[2 * node + 1], seg[2 * node + 2]);
  }
}

int lower_bound (int l, int r, int node, int delta) {
  if (seg[node].lazy != 0) push (l, r, node);
  if (l == r) return l;
  int mid = l + (r - l) / 2;
  push (l, mid, 2 * node + 1);
  if (seg[2 * node + 1].mx >= delta) {
    return lower_bound (l, mid, 2 * node +1, delta);
  }
  return lower_bound (mid + 1, r, 2 * node + 2, delta);
}

int upper_bound (int l, int r, int node, int delta) {
  if (seg[node].lazy != 0) push (l, r, node);
  if (l == r) return l;
  int mid = l + (r - l) / 2;
  push (l, mid, 2 * node + 1);
  if (seg[2 * node + 1].mx > delta) {
    return upper_bound (l, mid, 2 * node +1, delta);
  }
  return upper_bound (mid + 1, r, 2 * node + 2, delta);
}

int get (int l, int r, int node, int p) {
  if (seg[node].lazy != 0) push (l, r, node);
  if (l > p || r < p) return -1;
  if (l == p && r == p) return seg[node].mx;
  int mid = l + (r - l) / 2;
  return max (get (l, mid, 2 * node + 1, p), get (mid + 1, r, 2 * node + 2, p));
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  a[n] = 2e9;
  ++n;
  sort (a, a + n);
  build (0, n - 1, 0);
  while (q--) {
    char t;
    int lo, hi;
    cin >> t >> lo >> hi;
    if (t == 'F') {
      swap (lo, hi);
      int inicio = lower_bound (0, n - 1, 0, lo);
      int fim = min (n - 1, inicio + hi -1 );  
      int ultimo = get (0, n - 1, 0, fim);
      int ultimo_inicio = lower_bound (0, n - 1, 0, ultimo);
      int ultimo_fim = upper_bound (0, n - 1, 0, ultimo) - 1;   
      range_update (inicio, fim, 0, n - 1, 0, + 1);
      if (fim >= ultimo_inicio && fim < ultimo_fim) {     
        int tamanho = fim - ultimo_inicio;
        range_update (ultimo_inicio, ultimo_inicio + tamanho, 0, n - 1, 0, -1);
        range_update (ultimo_fim - tamanho, ultimo_fim, 0, n - 1, 0, +1);
      } 
    } else {
      cout << upper_bound (0, n - 1, 0, hi) -  lower_bound (0, n - 1, 0, lo) << '\n';
    }
  }
  return 0;
}

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