제출 #1213423

#제출 시각아이디문제언어결과실행 시간메모리
1213423orzorzorzGrowing Trees (BOI11_grow)C++20
100 / 100
79 ms1604 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100000; int n, q; int bit[MAXN + 10]; void add(int l, int r, int x) { if (l > r) return; for (int i = l; i < n; i |= i + 1) bit[i] += x; for (int i = r + 1; i < n; i |= i + 1) bit[i] -= x; } int query(int i) { int res = 0; for (; i >= 0; i = (i & (i + 1)) - 1) res += bit[i]; return res; } template<class T, class F> T firstTrue(T lo, T hi, F f) { ++hi; while (lo < hi) { T mid = lo + (hi - lo) / 2; if (f(mid)) { hi = mid; } else { lo = mid + 1; } } return lo; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); memset(bit, 0, sizeof(bit)); for (int i = 0; i < n; ++i) { add(i, i, a[i]); } for (int i = 0; i < q; ++i) { char ty; int x, y; cin >> ty >> x >> y; if (ty == 'F') { int c = x, h = y; int l = firstTrue(0, n - 1, [&](int idx) { return query(idx) >= h; }); if (l == n) continue; int r0 = l + c - 1; if (r0 >= n - 1) { add(l, n - 1, 1); } else { int x_val = query(r0); int l_ = firstTrue(l, n - 1, [&](int idx) { return query(idx) >= x_val; }); int r_ = firstTrue(l_, n - 1, [&](int idx) { return query(idx) > x_val; }) - 1; int cnt_first = l_ - l; int rem = c - cnt_first; if (cnt_first > 0) { add(l, l_ - 1, 1); } if (rem > 0) { int start = r_ - rem + 1; int end = r_; add(start, end, 1); } } } else { int min_val = x, max_val = y; int l_index = firstTrue(0, n - 1, [&](int idx) { return query(idx) >= min_val; }); int r_index = firstTrue(0, n - 1, [&](int idx) { return query(idx) > max_val; }); cout << (r_index - l_index) << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...