Submission #441305

#	Time	Username	Problem	Language	Result	Execution time	Memory
441305		SirCovidThe19th	Growing Trees (BOI11_grow)	C++14	100 / 100	328 ms	3348 KiB

grow

#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5+5;

int n, q, tmp[mx], bit[mx];

void upd(int l, int r, int val){
    for (; l <= n; l += l&(-l)) bit[l] += val;
    for (++r; r <= n; r += r&(-r)) bit[r] -= val;
}
int query(int i){
    int ret = 0;
    for (; i > 0; i -= i&(-i)) ret += bit[i];
    return ret;
}
int search(int val){ //index of first element greater/equal to val
    int low = 1, high = n+1;
    while (low < high){
        int mid = (low+high)/2;
        if (query(mid) >= val) high = mid;
        else low = mid+1;
    }return low;    
}

int main(){ 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> tmp[i];
    sort(tmp+1, tmp+n+1);
    for (int i = 1; i <= n; i++) upd(i, i, tmp[i]);
    while (q--){
        char t; int a, b; cin >> t >> a >> b; 
        if (t == 'F'){ 
            int l = search(b), r = l+a-1; 
            if (l > n) continue;
            else if (r >= n) upd(l, n, 1);
            else{
                int fr = search(query(r)), lr = search(query(r)+1)-1;
                upd(l, fr-1, 1); upd(lr-(r-fr), lr, 1);
            }  
        }else{
            int l = search(a), r = search(b+1)-1;
            cout<<r-l+1<<endl;
        }
    }
}

• 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