Submission #1255311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255311		Mer123haba456	Growing Trees (BOI11_grow)	C++20	100 / 100	112 ms	7940 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N lli(5e6)
#define MOD lli(1e9 + 7)
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef vector<plli> vplli;
typedef pair<lli, plli> pplli;
typedef vector<pplli> vpplli;

lli n,m,k,q,t;
vlli vect;

lli seg[N][3];

void yap(lli v, lli l,lli r){
    if(l == r){
        seg[v][1] = vect[r];
        seg[v][2] = vect[r];
        return;
    }
    lli m = (l+r)/2;
    yap(2*v,l,m);
    yap(2*v+1,m+1,r);
    seg[v][1] = max(seg[2*v][1], seg[2*v+1][1]);
    seg[v][2] = min(seg[2*v][2], seg[2*v+1][2]);
}

void gunc(lli v,lli l, lli r, lli istl, lli istr){
    if(istl<=l && r <= istr){
        seg[v][1]++;
        seg[v][0]++;
        seg[v][2]++;
        return;
    }
    lli m = (l+r)/2;
    if(istr<=m)
        gunc(2*v,l,m,istl,istr);
    else if(istl > m)
        gunc(2*v+1,m+1,r,istl,istr);
    else{
        gunc(2*v,l,m,istl,istr);
        gunc(2*v+1,m+1,r,istl,istr);
    }
    seg[v][1] = max(seg[2*v+1][1], seg[2*v][1]) + seg[v][0];
    seg[v][2] = min(seg[2*v+1][2], seg[2*v][2]) + seg[v][0];
}

lli getirBas(lli v,lli l,lli r,lli ist, lli art){
    if(l == r)
        return r;
    lli m = (l+r)/2;
    art += seg[v][0];
    if(seg[2*v][1] + art >= ist)
        return getirBas(2*v,l,m,ist, art);
    else
        return getirBas(2*v+1,m+1,r,ist, art);
}
lli getirSon(lli v,lli l,lli r,lli ist, lli art){
    if(l == r)
        return r;
    lli m = (l+r)/2;
    art += seg[v][0];
    if(ist >= seg[2*v+1][2] + art)
        return getirSon(2*v+1,m+1,r,ist, art);
    else
        return getirSon(2*v, l ,m ,ist, art);
}

lli getir(lli v,lli l,lli r, lli ist){
    if(l == r)
        return seg[v][1];
    lli m = (l+r)/2;
    if(ist<=m)
        return getir(2*v,l,m,ist) + seg[v][0];
    else
        return getir(2*v+1,m+1,r,ist) + seg[v][0];
}

int main()
{
    fast_io
    cin >> n >> q;
    for(lli i = 0;i<n;i++){
        cin >> k;
        vect.push_back(k);
    }
    sort(heps(vect));
    yap(1,0,n-1);
    while(q--){
        char c;
        cin >> c >> k >> m;
        if(c == 'F'){
            lli ind = getirBas(1,0,n-1,m, 0);
            lli say = getir(1,0,n-1,ind);
            if(say < m)
                continue;
            
            lli son = min(n-1, ind + k - 1);
            lli sonsay = getir(1,0,n-1,son);
            lli sonson = getirSon(1,0,n-1,sonsay, 0);
            if(son < sonson){
                lli sonilk = getirBas(1,0,n-1,sonsay, 0);
                lli su = son - sonilk + 1;
                gunc(1,0,n-1,sonson - su + 1,sonson);
                //cout << son << " " << sonsay << " " << sonson - su + 1 << " s" << sonson << endl;
                son = sonilk - 1;
                
            }
            if(ind > son)
                continue;
            //cout << ind << " " << son << endl;
            gunc(1,0,n-1,ind,son);
        }else{
            lli so = getirBas(1,0,n-1,k, 0);
            lli sosay = getir(1,0,n-1,n-1);
            if(k > sosay){
                cout << "0" << endl;
                continue;
            }
            
            lli sag = getirSon(1,0,n-1,m, 0);
            lli sagsay = getir(1,0,n-1,0);
            //cout << so << " " << sosay << " " << sag << " " << sagsay << endl;
            if(m < sagsay){
                cout << "0" << endl;
                continue;
            }
            cout << sag - so + 1 << endl;
        }
    }
}

• 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