oj.uz

Submission #956471

# Submission time Handle Problem Language Result Execution time Memory
956471 2024-04-02T03:45:36 Z eysbutno Growing Trees (BOI11_grow) C++11
100 / 100
 102 ms 3304 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
template<class T> class FenwickTree {
    private:
        int sz; vector<T> arr;
    public:
        FenwickTree(int n) {
            sz = n + 1, arr.resize(n + 1);
        }
        FenwickTree() {}
        T prefix(int idx) { // [0, idx] sum
            T tot = 0;
            for (++idx; idx >= 1; idx -= idx & -idx) {
                tot += arr[idx];
            }
            return tot;
        }
        T query(int l, int r) { // [l, r] sum
            return prefix(r) - prefix(l - 1);
        }
        void update(int idx, T dx) {
            for (++idx; idx < sz; idx += idx & -idx) {
                arr[idx] += dx;
            }
        }
};
FenwickTree<int> ft;
// global variable, so the lambdas work... lol
template<class T, class F> T firstTrue(T lo, T hi, F f) {
    ++hi; // returns hi + 1, if no result.
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        f(mid) ? hi = mid : lo = mid + 1;
    }
    return lo;
}
void solve() {
    int n, q; 
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) {
        cin >> i;
    }
    sort(all(a));
    ft = FenwickTree<int>(n + 1);
    for (int i = 0; i < n; i++) {
        ft.update(i, a[i]);
        ft.update(i + 1, -a[i]);
    }
    auto update = [&]() -> void {
        int c, h; cin >> c >> h;
        int l = firstTrue(0, n - 1, [&](int x) {
            return ft.prefix(x) >= h;
        }); 
        if (l == n) return;
        int r = l + c - 1;
        if (r >= n - 1) {
            ft.update(l, 1);
            ft.update(n, -1);
            return;
        }
        int edp = firstTrue(0, n - 1, [&](int x) {
            return ft.prefix(x) > ft.prefix(r);
        }); 
        if (r == edp - 1) {
            ft.update(l, 1);
            ft.update(edp, -1);
        } else {
            int split = firstTrue(0, n - 1, [&](int x) {
                return ft.prefix(x) >= ft.prefix(r);
            });
            ft.update(l, 1);
            ft.update(split, -1);
            int del = c - (split - l);
            ft.update(edp - del, 1);
            ft.update(edp, -1);
        }
    };
    auto query = [&]() -> void {
        int mn, mx; cin >> mn >> mx;
        int l = firstTrue(0, n - 1, [&](int x) {
            return ft.prefix(x) >= mn;
        });
        int r = firstTrue(0, n - 1, [&](int x) {
            return ft.prefix(x) > mx;
        });
        cout << r - l << "\n";
    };
    while (q--) {
        char c; cin >> c;
        (c == 'F') ? update() : query();
    }
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1; // cin >> t;
    while (t--) solve();
}
/**
 * 2011 - Growing Trees (Baltic OI)
 * Initially add every tree in. For each query, add
 * to a subsegment, such that the last element < h_i.
 * Then, handle the case h_i = a_i. In this case, do the
 * additions to the last few trees with h_i = a_i.
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2392 KB Output is correct
2 Correct 95 ms 2680 KB Output is correct
3 Correct 38 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 37 ms 1372 KB Output is correct
6 Correct 48 ms 1608 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 27 ms 1044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1620 KB Output is correct
2 Correct 49 ms 1872 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 31 ms 1432 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1876 KB Output is correct
2 Correct 49 ms 1616 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 44 ms 1872 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2148 KB Output is correct
2 Correct 86 ms 2412 KB Output is correct
3 Correct 13 ms 1112 KB Output is correct
4 Correct 33 ms 2392 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2140 KB Output is correct
2 Correct 84 ms 2288 KB Output is correct
3 Correct 39 ms 2532 KB Output is correct
4 Correct 15 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2132 KB Output is correct
2 Correct 65 ms 2492 KB Output is correct
3 Correct 37 ms 2644 KB Output is correct
4 Correct 13 ms 860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2756 KB Output is correct
2 Correct 86 ms 2384 KB Output is correct
3 Correct 23 ms 1812 KB Output is correct
4 Correct 61 ms 2224 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2640 KB Output is correct
2 Correct 91 ms 3256 KB Output is correct
3 Correct 102 ms 3012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3304 KB Output is correct