oj.uz

답안 #1088353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088353 2024-09-14T09:40:16 Z May27_th Growing Trees (BOI11_grow) C++17
10 / 100
 482 ms 9296 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;
      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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 299 ms 7504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 150 ms 1612 KB Output is correct
6 Incorrect 196 ms 2000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 190 ms 2120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 193 ms 2064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 299 ms 5812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 414 ms 6608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 351 ms 6688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 7764 KB Output is correct
2 Incorrect 452 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 402 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 9296 KB Output is correct