oj.uz

Submission #1088358

# Submission time Handle Problem Language Result Execution time Memory
1088358 2024-09-14T09:47:24 Z May27_th Growing Trees (BOI11_grow) C++17
100 / 100
 588 ms 9292 KB 
// #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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 7504 KB Output is correct
2 Correct 469 ms 7760 KB Output is correct
3 Correct 491 ms 7428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 149 ms 1720 KB Output is correct
6 Correct 194 ms 1980 KB Output is correct
7 Correct 13 ms 860 KB Output is correct
8 Correct 125 ms 1496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 2212 KB Output is correct
2 Correct 196 ms 2132 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 152 ms 1816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 2228 KB Output is correct
2 Correct 219 ms 2128 KB Output is correct
3 Correct 24 ms 856 KB Output is correct
4 Correct 199 ms 2112 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 5716 KB Output is correct
2 Correct 480 ms 6484 KB Output is correct
3 Correct 53 ms 1884 KB Output is correct
4 Correct 376 ms 6484 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 6484 KB Output is correct
2 Correct 454 ms 7032 KB Output is correct
3 Correct 482 ms 6736 KB Output is correct
4 Correct 58 ms 1968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 6992 KB Output is correct
2 Correct 332 ms 7504 KB Output is correct
3 Correct 478 ms 7416 KB Output is correct
4 Correct 58 ms 1880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 7760 KB Output is correct
2 Correct 445 ms 6816 KB Output is correct
3 Correct 67 ms 7768 KB Output is correct
4 Correct 366 ms 7512 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 7508 KB Output is correct
2 Correct 464 ms 7796 KB Output is correct
3 Correct 588 ms 8788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 9292 KB Output is correct