Submission #1213392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213392		orzorzorz	Growing Trees (BOI11_grow)	C++20	0 / 100	66 ms	3216 KiB

grow

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

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

const int mxN=1e5+1;

ll bit[mxN+1], a[mxN+1], d[mxN+1];
int n, m;

void upd(int pos, ll val) {
    for(; pos<=mxN; pos+=pos&-pos) {
        bit[pos]+=val;
    }
}

ll qry(int pos) {
    ll res=0;
    for(; pos; pos-=pos&-pos) {
        res+=bit[pos];
    }
    return res;
}

int f(ll val) {
    int l=1, r=n;
    while(l<=r) {
        int mid=(l+r)/2;
        if(qry(mid)>=val) {
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    return l;
}

int main() {
    ios::sync_with_stdio(0); cin.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++) {
        d[i]=a[i]-a[i-1];
        upd(i, d[i]);
    }
    for(int i=0; i<m; i++) {
        char ty; cin>>ty;
        if(ty == 'F') {
            int c, h; cin >> c >> h;
            int left = f(h), right = left + c - 1;
            if(left == n + 1) continue;
            if(right > n) {
                upd(left, 1);
                upd(n + 1, -1);
            } else {
                upd(left, 1);
                upd(right + 1, -1);
            }
        } else {
            ll x, y; cin>>x>>y;
            int l=f(x), r=f(y+1);
            if(l==n+1) {
                cout<<0<<"\n";
            } else { 
                if(r==n+1) r--;
                cout<<r-l+1<<"\n";
            }
        }
    }
    return 0;
}
//rating below 2400 must be solved orzorzorz

• 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