Submission #1038919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038919		BF001	Growing Trees (BOI11_grow)	C++17	100 / 100	76 ms	4176 KiB

grow

#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define int long long

int n, m, bit[N], a[N];

void ud(int l, int r, int val){
    if (l > r) return;
    while (l <= n){
        bit[l] += val;
        l += (l & (-l));
    }
    r++;
    while (r <= n){
        bit[r] -= val;
        r += (r & (-r));
    }
}

int get(int pos){
    int rt = 0;
    while (pos >= 1){
        rt += bit[pos];
        pos -= (pos & (-pos));
    }
    return rt;
}
 
int bin(int val){
    int rt = n + 1;
    int l = 1, r = n;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (get(mid) >= val){
            rt = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    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++){
        ud(i, i, a[i]);
    }

    while (m--){
        char typ;
        cin >> typ;
        if (typ == 'F'){
            int c, h;
            cin >> c >> h;
            int l = bin(h);
            if (l == n + 1) continue;
            int r = l + c - 1;
            if (r >= n){
                ud(l, n, 1);
                continue;
            }
            int l2 = bin(get(r)) - 1;
            int r2 = bin(get(r) + 1) - 1;
            ud(l, l2, 1);
            l2 = r2 - (c - (l2 - l + 1)) + 1;
            ud(l2, r2, 1);
            continue;
        }
        int l, r;
        cin >> l >> r;
        l = bin(l);
        r = bin(r + 1) - 1;
        cout << r - l + 1 << "\n";
    }
 
    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