제출 #1213409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213409		timeflew	Growing Trees (BOI11_grow)	C++20	0 / 100	68 ms	3140 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 if(qry(right)!=qry(right+1)) {
                upd(left, 1);
                upd(right+1, -1);
            } else {
                ll val=qry(right);
                int newl=f(val);
                upd(left, 1);
                upd(newl, -1);
                int newr=f(val+1);//[newr-1-count+1 ,newr-1] count is equal to newl-left
                upd(newr-(newl-left), 1);
                upd(newr, -1);
            }
        } else {
            ll x, y; cin>>x>>y;
            int l=f(x), r=f(y+1);
            if(l==n+1) {
                cout<<0<<"\n";
            } else { 
                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