Submission #624508

#	Time	Username	Problem	Language	Result	Execution time	Memory
624508		kakayoshi	Growing Trees (BOI11_grow)	C++17	100 / 100	135 ms	2952 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
typedef long long int ll;
const ll maxN=5e5+5;
const ll mod=1e9+7;
const ll oo=1e18;
struct fenwick
{
    int n;
    vector <int> fen;
    fenwick(int _n=1e5)
    {
        n=_n;
        fen.assign(n+5,0);
    }
    void update(int pos, int val)
    {
        for(;pos<=n;pos+=pos&-pos) fen[pos]+=val;
        return;
    }
    void update(int l, int r, int val)
    {
        update(l,val);
        update(r+1,-val);
        return;
    }
    int get(int pos)
    {
        int ans=0;
        for(;pos;pos-=pos&-pos) ans+=fen[pos];
        return ans;
    }
}fen;
int n,q,a[maxN];
int find_pos(int val)
{
    int l=1;
    int r=n;
    int ans=n+1;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (fen.get(mid)>=val)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
void solve()
{
    cin>>n>>q;
    forw(i,1,n)
        cin>>a[i];
    sort(a+1,a+1+n);
    forw(i,1,n)
        fen.update(i,i,a[i]);
    while (q--)
    {
        char c; cin>>c;
        if (c=='F')
        {
            int c,h; cin>>c>>h;
            int l=find_pos(h);
            if (l==n+1) continue;
            c=min(c,n-l+1);
            int r=l+c-1;
            if (r<n && fen.get(r)==fen.get(r+1))
            {
                h=fen.get(r);
                int pos=find_pos(h);
                int add=r-pos+1;
                r=pos-1;
                fen.update(l,r,1);
                pos=find_pos(h+1);
                fen.update(pos-add,pos-1,1);
            }
            else
                fen.update(l,r,1);
        }
        else
        {
            int l,r; cin>>l>>r;
            cout<<find_pos(r+1)-find_pos(l)<<"\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    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