제출 #1166915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166915		fryingduc	Growing Trees (BOI11_grow)	C++20	90 / 100	1095 ms	4376 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;
pair<int, int> tree[maxn << 2];
int lazy[maxn << 2];

pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b) {
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}

void down(int ind, int l, int r) {
  tree[ind].first += lazy[ind];
  tree[ind].second += lazy[ind];
  if (l != r) {
    lazy[ind << 1] += lazy[ind];
    lazy[ind << 1 | 1] += lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, int val, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] += val;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, val, ind << 1, l, mid);
  update(x, y, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

pair<int, int> get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return make_pair(2e9, -1);
  if (x <= l and r <= y) return tree[ind];
  int mid = (l + r) >> 1;
  return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}

pair<int, int> stretch(int p) {
  int bl = p, br = p;
  int l = p, r = n;
  int v = get(p, p).second;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (get(p, mid).second == 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, p).first == 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());
//  debug(vx);
  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, mid).first >= 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);
//      debug(p, rg);
      if (p <= rg.first - 1) {
        update(p, rg.first - 1, 1);
      }
      c -= (rg.first - p);
      update(rg.second - c + 1, rg.second, 1);
//      for (int i = 1; i <= n; ++i) {
//        cout << get(i, i).first << " ";
//      }
//      cout << '\n';
    } 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, mid).second >= 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, mid).second <= 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: 0 / 10
• Subtask 10: 10 / 10