Submission #1165345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165345		Hanksburger	Growing Trees (BOI11_grow)	C++20	100 / 100	214 ms	2376 KiB

grow

#include <bits/stdc++.h>
using namespace std;
int a[100005], seg[400005], n, m;
void update(int i, int l, int r, int ql, int qr, int x)
{
    if (ql<=l && r<=qr)
    {
        seg[i]+=x;
        return;
    }
    int mid=(l+r)/2;
    if (l<=qr && ql<=mid)
        update(i*2, l, mid, ql, qr, x);
    if (mid<qr && ql<=r)
        update(i*2+1, mid+1, r, ql, qr, x);
}
int query(int i, int l, int r, int x)
{
    if (l==r)
        return seg[i];
    int mid=(l+r)/2;
    return seg[i]+(x<=mid?query(i*2, l, mid, x):query(i*2+1, mid+1, r, x));
}
int lowerBound(int x)
{
    int l=1, r=n+1;
    while (l<r)
    {
        int mid=(l+r)/2;
        if (query(1, 1, n, mid)<x)
            l=mid+1;
        else
            r=mid;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    sort(a+1, a+n+1);
    for (int i=1; i<=n; i++)
        update(1, 1, n, i, i, a[i]);
    for (int i=1; i<=m; i++)
    {
        char x;
        cin >> x;
        if (x=='F')
        {
            int c, h;
            cin >> c >> h;
            int ind=lowerBound(h);
            if (ind>n)
                continue;
            if (ind+c>n)
            {
                update(1, 1, n, ind, n, 1);
                continue;
            }
            int val=query(1, 1, n, ind+c-1);
            int ind2=lowerBound(val), ind3=lowerBound(val+1);
            if (ind<ind2)
                update(1, 1, n, ind, ind2-1, 1);
            update(1, 1, n, ind3-(ind+c-ind2), ind3-1, 1);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << lowerBound(r+1)-lowerBound(l) << '\n';
        }
    }
}

• 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