oj.uz

Submission #225513

# Submission time Handle Problem Language Result Execution time Memory
225513 2020-04-20T17:02:28 Z Haunted_Cpp Growing Trees (BOI11_grow) C++17
100 / 100
 173 ms 6172 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5240 KB Output is correct
2 Correct 133 ms 5688 KB Output is correct
3 Correct 96 ms 5496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct
3 Correct 8 ms 3584 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 48 ms 4600 KB Output is correct
6 Correct 57 ms 4856 KB Output is correct
7 Correct 11 ms 3584 KB Output is correct
8 Correct 34 ms 4344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4856 KB Output is correct
2 Correct 61 ms 4984 KB Output is correct
3 Correct 7 ms 3584 KB Output is correct
4 Correct 47 ms 4472 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4984 KB Output is correct
2 Correct 64 ms 4860 KB Output is correct
3 Correct 15 ms 3584 KB Output is correct
4 Correct 58 ms 5112 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4984 KB Output is correct
2 Correct 126 ms 5112 KB Output is correct
3 Correct 20 ms 3968 KB Output is correct
4 Correct 74 ms 5112 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4984 KB Output is correct
2 Correct 119 ms 5240 KB Output is correct
3 Correct 93 ms 5368 KB Output is correct
4 Correct 19 ms 3968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4984 KB Output is correct
2 Correct 97 ms 5224 KB Output is correct
3 Correct 104 ms 5496 KB Output is correct
4 Correct 20 ms 3968 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5624 KB Output is correct
2 Correct 130 ms 5240 KB Output is correct
3 Correct 38 ms 4892 KB Output is correct
4 Correct 92 ms 5072 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5368 KB Output is correct
2 Correct 115 ms 5496 KB Output is correct
3 Correct 173 ms 5752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 6172 KB Output is correct