Submission #994401

#	Time	Username	Problem	Language	Result	Execution time	Memory
994401		Khanhcsp2	Growing Trees (BOI11_grow)	C++14	100 / 100	461 ms	5240 KiB

grow

#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
int n, q, a[N], nod[4*N];
void update(int id, int l, int r, int a, int b, int v)
{
    if(l>b || r<a) return;
    if(a<=l && r<=b)
    {
        nod[id]+=v;
        return;
    }
    int mid=(l+r)/2;
    update(id*2, l, mid, a, b, v);
    update(id*2+1, mid+1, r, a, b, v);
//    nod[id]=(nod[id*2]+ nod[id*2+1]);
}
int get(int id, int l, int r, int a, int b)
{
    if(l>b || r<a) return 0;
    if(a<=l && r<=b) return nod[id];
    int mid=(l+r)/2;
    return nod[id]+get(id*2, l, mid, a, b)+get(id*2+1, mid+1, r, a, b);
}
int f1(int x)
{
    int l=1, r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(get(1, 1, n, mid, mid)>=x)
        {
            r=mid-1;
        }
        else l=mid+1;
    }
    return l;
}
int f2(int x)
{
    int l=1, r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(get(1, 1, n, mid, mid)>x)
        {
            r=mid-1;
        }
        else l=mid+1;
    }
    return l;
}
void sol()
{
    cin >> n >> q;
    for(int i=1, x; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) update(1, 1, n, i, i, a[i]);
    while(q--)
    {
        char tt;
        cin >> tt;
        if(tt=='F')
        {
            int u, v;
            cin >> u >> v;
            int pos=f1(v);
            if(pos<=n)
            {
                int p=min(pos+u-1,n);
                int l=f1(get(1,1,n,p,p));
                int r=f2(get(1,1,n,p,p));
                int need=p-l+1;
                update(1,1,n,pos,l-1,1);
                update(1,1,n,r-need,r-1,1);
            }
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << f2(r)-f1(l) << el;
        }
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Compilation message (stderr)

grow.cpp: In function 'void sol()':
grow.cpp:66:18: warning: unused variable 'x' [-Wunused-variable]
   66 |     for(int i=1, x; i<=n; i++) cin >> a[i];
      |                  ^

• 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