Submission #1256902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256902		chikien2009	Growing Trees (BOI11_grow)	C++20	0 / 100	76 ms	1736 KiB

grow

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct FENWICK_TREE
{
    int tree[100001];
    inline FENWICK_TREE()
    {
        fill_n(tree, 1e5 + 1, 0);
    }
    inline void Update(int x, int v)
    {
        while (x <= 1e5)
        {
            tree[x] += v;
            x += (x & (~(x - 1)));
        }
    }
    inline int Get(int x)
    {
        int res = 0;
        while (0 < x)
        {
            res += tree[x];
            x -= (x & (~(x - 1)));
        }
        return res;
    }
} ft;

int n, q, a[100001], b, c, d, e, f;
char t;

inline int Pos(int lim)
{
    int l = 1, r = n, m, res = n + 1;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (ft.Get(m) >= lim)
        {
            res = m;
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return res;
}

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i)
    {
        ft.Update(i, a[i] - a[i - 1]);
    }
    while (q--)
    {
        cin >> t >> b >> c;
        if (t == 'F')
        {
            d = Pos(c);
            if (d == n + 1)
            {
                continue;
            }
            e = Pos(ft.Get(min(n, d + b)));
            ft.Update(d, 1);
            ft.Update(e, -1);
            b -= e - d;
            e = Pos(ft.Get(e) + 1);
            ft.Update(e, -1);
            ft.Update(max(d, e - b), 1);
        }
        else
        {
            b = Pos(b);
            c = Pos(c + 1);
            cout << c - b << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10