Submission #1258522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258522		thecyb	Growing Trees (BOI11_grow)	C++17	100 / 100	82 ms	1604 KiB

grow

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second

struct node {
  int count = 0;
  int on_edge = 0;
  node(const int &c, const int &o) : count(c), on_edge(o) {}
  node combine(const node &other) {
    return (node(count + other.count, other.on_edge));
  }
};

const int N = 100003;

int bit[N];

void upd(int l, int r, int k) {
  if (r < l)
    return;
  for (; l < N; l += l & -l) {
    bit[l] += k;
  }
  r++;
  for (; r < N; r += r & -r)
    bit[r] -= k;
}

int firstTrue(int l, int r, std::function<bool(int)> check) {
  r++;
  while (l < r) {
    int m = l + ((r - l) >> 1);
    if (check(m))
      r = m;
    else
      l = m + 1;
  }
  return l;
}

int query(int x) {
  int ret = 0;
  for (; x > 0; x -= x & -x)
    ret += bit[x];
  return ret;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n);
  for (int &i : a)
    std::cin >> i;
  std::sort(a.begin(), a.end());
  memset(bit, 0, sizeof bit);
  for (int i = 0; i < n; i++)
    upd(i + 1, i + 1, a[i]);
  for (int i = 0; i < q; i++) {
    char type;
    int x, y;
    std::cin >> type >> x >> y;
    if (type == 'F') {
      int l =
          firstTrue(1, n, [&](const int &x) -> bool { return query(x) >= y; });
      if (l == n + 1)
        continue;
      int r = std::min(n + 1, l + x - 1);
      if (r >= n) {
        upd(l, n, 1);
      } else {
        int target = query(r);
        int l2 = firstTrue(
            l, n, [&](const int &i) -> bool { return query(i) >= target; });
        int r2 =
            firstTrue(l2, n,
                      [&](const int &i) -> bool { return query(i) > target; }) -
            1;
        upd(l, l2 - 1, 1);
        upd(r2 - (x - (l2 - l)) + 1, r2, 1);
      }
    } else {
      int l =
          firstTrue(1, n, [&](const int i) -> bool { return query(i) >= x; });
      int r =
          firstTrue(1, n, [&](const int i) -> bool { return query(i) > y; });
      std::cout << r - l << '\n';
    }
  }
}

• 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