oj.uz

답안 #414015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414015 2021-05-29T18:46:23 Z Alex_tz307 Growing Trees (BOI11_grow) C++17
100 / 100
 142 ms 3268 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN];

struct SegTree {
  int Size;
  vector<int> tree, lazy;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1);
    lazy.resize(Size << 1);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      tree[x] = a[lx];
      return;
    }
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    build(lSon, lx, mid);
    build(rSon, mid + 1, rx);
    tree[x] = max(tree[lSon], tree[rSon]);
  }

  void push(int x) {
    if (lazy[x] == 0)
      return;
    for (int i = 0; i < 2; ++i) {
      int son = x << 1 | i;
      tree[son] += lazy[x];
      lazy[son] += lazy[x];
    }
    lazy[x] = 0;
  }

  void update(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      ++tree[x], ++lazy[x];
      return;
    }
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (st <= mid)
      update(lSon, lx, mid, st, dr);
    if (mid < dr)
      update(rSon, mid + 1, rx, st, dr);
    tree[x] = max(tree[lSon], tree[rSon]);
  }

  int get_first_greater_equal(int x, int lx, int rx, int val) {
    if (lx == rx)
      return lx;
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (tree[lSon] >= val)
      return get_first_greater_equal(lSon, lx, mid, val);
    return get_first_greater_equal(rSon, mid + 1, rx, val);
  }

  int get_first_greater(int x, int lx, int rx, int val) {
    if (lx == rx)
      return lx;
    push(x);
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (tree[lSon] > val)
      return get_first_greater(lSon, lx, mid, val);
    return get_first_greater(rSon, mid + 1, rx, val);
  }

  int get_val(int x, int lx, int rx, int poz) {
    if (lx == rx)
      return tree[x];
    push(x);
    int mid = (lx + rx) >> 1;
    if (poz <= mid)
      return get_val(x << 1, lx, mid, poz);
    return get_val(x << 1 | 1, mid + 1, rx, poz);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  for (int i = 1; i <= N; ++i)
    cin >> a[i];
  sort(a + 1, a + N + 1);
  a[++N] = INF;
  SegTree tree(N);
  tree.build(1, 1, N);
  for (int q = 0; q < Q; ++q) {
    char t;
    int x, y;
    cin >> t >> x >> y;
    if (t == 'F') {
      int first_poz = tree.get_first_greater_equal(1, 1, N, y);
      if (first_poz == N)
        continue;
      int last_poz = first_poz + x - 1;
      if (last_poz >= N) {
        tree.update(1, 1, N, first_poz, N - 1);
        continue;
      }
      int val = tree.get_val(1, 1, N, last_poz);
      int last_poz_update = tree.get_first_greater_equal(1, 1, N, val) - 1;
      if (first_poz <= last_poz_update)
        tree.update(1, 1, N, first_poz, last_poz_update);
      int rem = last_poz - last_poz_update;
      if (rem == 0)
        continue;
      last_poz_update = tree.get_first_greater(1, 1, N, val) - 1;
      tree.update(1, 1, N, last_poz_update - rem + 1, last_poz_update);
    } else cout << tree.get_first_greater(1, 1, N, y) - tree.get_first_greater_equal(1, 1, N, x) << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 2832 KB Output is correct
2 Correct 111 ms 2824 KB Output is correct
3 Correct 106 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 42 ms 612 KB Output is correct
6 Correct 50 ms 944 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 27 ms 716 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 812 KB Output is correct
2 Correct 51 ms 868 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 32 ms 720 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 824 KB Output is correct
2 Correct 55 ms 804 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 52 ms 836 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 1676 KB Output is correct
2 Correct 104 ms 2824 KB Output is correct
3 Correct 16 ms 992 KB Output is correct
4 Correct 88 ms 2640 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 2680 KB Output is correct
2 Correct 115 ms 2780 KB Output is correct
3 Correct 108 ms 2640 KB Output is correct
4 Correct 15 ms 952 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 2876 KB Output is correct
2 Correct 75 ms 3012 KB Output is correct
3 Correct 118 ms 2668 KB Output is correct
4 Correct 15 ms 972 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 2820 KB Output is correct
2 Correct 103 ms 2756 KB Output is correct
3 Correct 30 ms 2764 KB Output is correct
4 Correct 58 ms 2748 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 2872 KB Output is correct
2 Correct 104 ms 2776 KB Output is correct
3 Correct 142 ms 2764 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 3268 KB Output is correct