Submission #638212

#	Time	Username	Problem	Language	Result	Execution time	Memory
638212		finn__	Growing Trees (BOI11_grow)	C++17	100 / 100	262 ms	3916 KiB

grow

#include <bits/stdc++.h>
using namespace std;

struct fenwick_tree
{
    vector<long> tree;
    size_t l;

    fenwick_tree(size_t n)
    {
        l = n;
        tree = vector<long>(1 << (32 - __builtin_clz(n)), 0);
    }

    void update(size_t i, long x)
    {
        i++;
        while (i <= tree.size())
        {
            tree[i - 1] += x;
            i += i & -i;
        }
    }

    long prefix_sum(size_t i)
    {
        i++;
        long x = 0;
        while (i)
        {
            x += tree[i - 1];
            i -= i & -i;
        }
        return x;
    }
};

size_t ftree_lower_bound(fenwick_tree &t, long x)
{
    size_t a = 0, b = t.l;

    while (a < b)
    {
        size_t mid = (a + b) / 2;
        if (t.prefix_sum(mid) < x)
            a = mid + 1;
        else
            b = mid;
    }

    return a;
}

size_t ftree_upper_bound(fenwick_tree &t, long x)
{
    size_t a = 0, b = t.l;

    while (a < b)
    {
        size_t mid = (a + b) / 2;
        if (t.prefix_sum(mid) <= x)
            a = mid + 1;
        else
            b = mid;
    }

    return a;
}

int main()
{
    size_t n, m;
    cin >> n >> m;

    vector<long> seq(n);
    for (long &x : seq)
        cin >> x;

    sort(seq.begin(), seq.end());
    fenwick_tree tree(n);
    tree.update(0, seq[0]);
    for (size_t i = 1; i < n; i++)
        tree.update(i, seq[i] - seq[i - 1]);

    for (size_t i = 0; i < m; i++)
    {
        char t;
        cin >> t;

        switch (t)
        {
        case 'F':
        {
            long c, h;
            cin >> c >> h;
            size_t l = ftree_lower_bound(tree, h);
            size_t r = min(l + c - 1, tree.l - 1);
            if (r == tree.l - 1)
            {
                tree.update(l, 1);
            }
            else
            {
                size_t y = ftree_upper_bound(tree, tree.prefix_sum(r));
                size_t x = ftree_lower_bound(tree, tree.prefix_sum(r)) - 1;
                tree.update(y - (r - x), 1);
                if (y < tree.l)
                    tree.update(y, -1);
                tree.update(l, 1);
                tree.update(x + 1, -1);
            }
            break;
        }
        case 'C':
        {
            long hmin, hmax;
            cin >> hmin >> hmax;

            size_t l = ftree_lower_bound(tree, hmin);
            size_t r = ftree_upper_bound(tree, hmax);

            cout << (r - l) << '\n';
            break;
        }
        }
    }
}

• 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