Submission #1011439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011439		doducanh	Growing Trees (BOI11_grow)	C++14	100 / 100	71 ms	3372 KiB

grow

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn];
int n,q;
struct BIT{
    int n;
    vector<int>t;
    BIT(){}
    BIT(int n):n(n),t(n+7,0){}
    void up(int x,int val){
        for(;x<=n;x+=(x&(-x)))t[x]+=val;
    }
    void add(int l,int r,int val){
        up(l,val);
        up(r+1,-val);
    }
    int get(int x){
        int ans=0;
        for(;x;x-=(x&(-x)))ans+=t[x];
        return ans;
    }
};
BIT t;
int Findthefirst(int val){
    int l=1,r=n;
    int res=n+1;
    while(l<=r){
        int m=(l+r)/2;
        if(t.get(m)>=val){
            res=m;
            r=m-1;
        }
        else l=m+1;
    }
    return res;
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    t=BIT(n);
    for(int i=1;i<=n;i++){
        t.add(i,i,a[i]);
    }
    while(q--){
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='F'){
            int l=Findthefirst(b);
            int r=l+a-1;
            if(r>n){
                t.add(l,n,1);
                continue;
            }
            int x=t.get(r);
            int l_=Findthefirst(x);
            int r_=Findthefirst(x+1)-1;
            t.add(l,l_-1,1);
            t.add(r_-(a-(l_-l))+1,r_,1);
        }
        else{
            int l=Findthefirst(a);
            int r=Findthefirst(b+1);
            cout<<r-l<<"\n";
        }
    }
}

Compilation message (stderr)

grow.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

• 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