Submission #1163631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163631		DangKhoizzzz	Growing Trees (BOI11_grow)	C++20	100 / 100	107 ms	1604 KiB

grow

#include <bits/stdc++.h>
// #define int long long

using namespace std;

const int maxn = 1e5 + 7;


struct Fenwick_Tree
{
    vector <int> tree = vector <int> (maxn , 0);

    void update(int pos , int val)
    {
        while(pos < (int)tree.size())
        {
            tree[pos] += val;
            pos += (pos & (-pos));
        }
    }

    int get_prefix(int pos)
    {
        int sum = 0;
        while(pos > 0)
        {
            sum += tree[pos];
            pos -= (pos & (-pos));
        }
        return sum;
    }

    int get_range(int l , int r)
    {
        return get_prefix(r) - get_prefix(l-1);
    }
} bit;


int n , q , a[maxn];

int find_pos(int val)
{
    int l = 1 , r = n , pos = n+1;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(bit.get_prefix(mid) >= val)
        {
            pos = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return pos;
}

void solve_case1()
{
    int reqh , cnt; cin >> cnt >> reqh;

    int L = find_pos(reqh);

    if(L + cnt - 1 > n)
    {
        bit.update(L , 1);
        bit.update(n+1 , -1);
        return;
    }

    int edv = bit.get_prefix(L + cnt - 1);
    int R = find_pos(edv) - 1;
    int FR = find_pos(edv + 1) - 1;

    bit.update(L , 1);
    bit.update(R+1 , -1);

    bit.update(FR+1 , -1);
    bit.update(FR - (cnt - (R - L + 1)) + 1 , 1);
}

void solve_case2()
{
    int L , R; cin >> L >> R;
    cout << find_pos(R+1) - find_pos(L) << '\n';
}


void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1 , a+n+1);
    for(int i = 1; i <= n; i++)
    {
        bit.update(i , a[i] - a[i-1]);
    }

    while(q--)
    {
        char type; cin >> type;

        if(type == 'F')
        {
            solve_case1();
        }
        else
        {
            solve_case2();
        }

        //for(int i = 1; i <= n; i++) cout << bit.get_prefix(i) << ' ';
        //cout << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt" , "r" , stdin);
    //freopen("out.txt" , "w" , stdout);
    solve();
    return 0;
}

• 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