Submission #1166916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166916		fryingduc	Growing Trees (BOI11_grow)	C++20	100 / 100	71 ms	2320 KiB

grow

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m;

long long bit[maxn];

void update(int i, int val) {
  for (; i <= n; i += i & (-i)) {
    bit[i] += val;
  }
}

void update(int l, int r, int val) {
  update(l, val);
  if (r < n) {
    update(r + 1, -val);
  }
}

long long get(int i) {
  long long ans = 0;
  for (; i > 0; i -= i & (-i)) {
    ans += bit[i];
  } 
  return ans;
}

pair<int, int> stretch(int p) {
  int bl = p, br = p;
  int l = p, r = n;
  int v = get(p);
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (get(mid) == v) {
      br = mid, l = mid + 1;
    } else r = mid - 1;
  }
  l = 1, r = p;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (get(mid) == v) {
      bl = mid, r = mid - 1;
    } else l = mid + 1;
  }
  return make_pair(bl, br);
}

void solve() {
  cin >> n >> m;
  vector<int> vx(n);
  for (auto &i : vx) cin >> i;
  sort(vx.begin(), vx.end());
  for (int i = 0; i < n; ++i) {
    update(i + 1, i + 1, vx[i]);
  }
  while (m--) {
    char t; cin >> t;
    if (t == 'F') {
      int c, h; cin >> c >> h;
      int l = 1, r = n, p = -1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (get(mid) >= h) {
          p = mid, r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      if (p == -1) continue;
      c = min(c, n - p + 1);
      pair<int, int> rg = stretch(p + c - 1);
      if (p <= rg.first - 1) {
        update(p, rg.first - 1, 1);
      }
      c -= (rg.first - p);
      update(rg.second - c + 1, rg.second, 1);
    } else {
      int u, v; cin >> u >> v;
      int l = 1, r = n, p = -1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (get(mid) >= u) {
          p = mid, r = mid - 1;
        } else l = mid + 1;
      }
      if (p == -1) {
        cout << 0 << '\n';
        continue;
      }
      int q = -1;
      l = p, r = n;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (get(mid) <= v) {
          q = mid, l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      cout << (q == -1 ? 0 : q - p + 1) << '\n';
    }

  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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