Submission #1088358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088358		May27_th	Growing Trees (BOI11_grow)	C++17	100 / 100	588 ms	9292 KiB

grow

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 5;
int a[MAXN];
struct DataTree {
  const i64 INF = 1e18;
  struct Data {
    i64 v, lz;
  };
  vector<Data> st;
  DataTree (int _N) : st(4 * _N + 4) {}
  Data combine(Data lf, Data rg) {
    Data res;
    res.v = lf.v + rg.v;
    res.lz = 0;
    return res;
  }
  void build(int id, int l, int r) {
    if (l == r) {
      st[id].v = a[l];
      st[id].lz = 0;
      return;
    }
    int mid = (l + r)/2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
    // cout << id << " " << st[id].v << " " << st[id].lz << "\n";
  }
  void push(int id, int l, int r) {
    i64 &add = st[id].lz;
    int mid = (l + r)/2;
    st[id * 2].v += add * (l - mid + 1);
    st[id * 2 + 1].v += add * (r - mid);
    st[id * 2].lz += add;
    st[id * 2 + 1].lz += add;
    add = 0;
    return;
  }
  void update(int id, int l, int r, int u, int v, i64 x) {
    if (v < l || u > r) return;
    if (u <= l && r <= v) {
      st[id].v += x * (r - l + 1);
      st[id].lz += x;
      return;
    }
    push(id, l, r);
    int mid = (l + r)/2;
    update(id * 2, l, mid, u, v, x);
    update(id * 2 + 1, mid + 1, r, u, v, x);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
  }
  Data get(int id, int l, int r, int u, int v) {
    if (v < l || u > r) return {0, 0};
    if (u <= l && r <= v) return st[id];
    push(id, l, r);
    int mid = (l + r)/2;
    return combine(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
  }
};
void Solve(void) {
  int N, Q; cin >> N >> Q;
  for (int i = 1; i <= N; i ++) cin >> a[i];
  sort(a + 1, a + N + 1);
  DataTree T(N + 2); T.build(1, 1, N);
  while (Q --) {
    char op; int C, H; cin >> op >> C >> H;
    if (op == 'F') {
      int l = 1, h = N;
      while (l <= h) {
        int mid = (l + h)/2;
        if (T.get(1, 1, N, mid, mid).v >= H) h = mid - 1;
        else l = mid + 1;
      }
      // l = first to increase
      int lf = l;
      if (lf > N) continue;
      int rg = min(l + C - 1, N);
      int mx = T.get(1, 1, N, rg, rg).v;
      // find the biggest id that = mx
      l = 1, h = N;
      while (l <= h) {
        int mid = (l + h)/2;
        if (T.get(1, 1, N, mid, mid).v > mx) h = mid - 1;
        else l = mid + 1;
      }
      int rgg = h;

      // find the smallest id that = mx
      l = 1, h = N;
      while (l <= h) {
        int mid = (l + h)/2;
        if (T.get(1, 1, N, mid, mid).v >= mx) h = mid - 1;
        else l = mid + 1;
      }
      int lff = l;
      int gap = rg - lff + 1;
      // cout << mx << "\n";
      // cout << lf << " " << lff - 1 << " " << rgg - gap + 1 << " " << rgg << "\n";

      T.update(1, 1, N, lf, lff - 1, 1);
      T.update(1, 1, N, rgg - gap + 1, rgg, 1);
    } else {
      int l = 1, h = N;
      while (l <= h) {
        int mid = (l + h)/2;
        if (T.get(1, 1, N, mid, mid).v >= C) h = mid - 1;
        else l = mid + 1;
      }
      int lf = l;

      l = 1, h = N;
      while (l <= h) {
        int mid = (l + h)/2;
        if (T.get(1, 1, N, mid, mid).v > H) h = mid - 1;
        else l = mid + 1;
      }

      cout << h - lf + 1 << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

• 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