Submission #1280407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280407		ngocphu	Growing Trees (BOI11_grow)	C++20	0 / 100	81 ms	2360 KiB

grow

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 1e5 + 4;

int n, q, a[maxN], diff[maxN];
ll bit[maxN];

void update(int x, ll v)
{
    for (; x <= n; x += x & -x) bit[x] += v;
}

ll get(int x)
{
    ll res = 0;
    for (; x >= 1; x -= x & -x) res += bit[x];
    return res;
}

int fi(ll x)
{
    int l = 1, r = n, ans = -1;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (get(m) >= x)
        {
            ans = m;
            r = m - 1;
        }
        else l = m + 1;
    }

    return ans;
}

pair<int,int> process(ll x)
{
    pair<int,int> res = make_pair(0, 0);
    int l = 1, r = n, ans = -1;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (get(m) >= x)
        {
            ans = m;
            r = m - 1;
        }
        else l = m + 1;
    }

    res.first = ans;

    l = 1, r = n, ans = -1;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (get(m) <= x)
        {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }

    res.second = ans;

    return res;
}

int query(ll mn, ll mx)
{
    int l = 1, r = n, Left = n + 4, Right = 0;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (get(m) >= mn)
        {
            Left = m;
            r = m - 1;
        }
        else l = m + 1;
    }

    l = 1, r = n;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (get(m) <= mx)
        {
            Right = m;
            l = m + 1;
        }
        else r = m - 1;
    }

    return max(0, Right - Left + 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen(".INP","r",stdin);
    // freopen(".OUT","w",stdout);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    sort(a + 1, a + n + 1);

    diff[1] = a[1];
    update(1, diff[1]);

    for (int i = 2; i <= n; ++i)
    {
        diff[i] = a[i] - a[i - 1];
        update(i, diff[i]);
    }

    for (int i = 1; i <= q; ++i)
    {
        char t; cin >> t;

        if (t == 'F')
        {
            int c; cin >> c;
            ll h; cin >> h;
            int l = fi(h);

            if (l == -1) continue;

            int r = min(l + c - 1, n);

            pair<int,int> tmp = process(get(r));

            int l2 = tmp.first, r2 = tmp.second;

            update(l, 1);
            update(l2, -1);

            update(r2 - (c - (l2 - l)) + 1, 1);
            update(r2 + 1, -1);
        }
        else
        {
            ll mn, mx; cin >> mn >> mx;
            cout << query(mn, mx) << "\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