Submission #725471

#	Time	Username	Problem	Language	Result	Execution time	Memory
725471		smirichto	Growing Trees (BOI11_grow)	C++17	0 / 100	194 ms	16924 KiB

grow

#include <bits/stdc++.h>

using namespace std;

const long long N = 2e5 + 5 ;

#define ll long long
#define endl '\n'

struct segmentTree {
    int n;
    vector<ll> sum, lz, sumB , maxi , mini;
    void init(int _n, int b[]) {
        n = _n;
        sum.assign(4 * n + 6, 0);
        lz.assign(4 * n + 6, 0);
        sumB.assign(4 * n + 6, 0);
        maxi.assign(4 * n + 6, -1e17);
        mini.assign(4 * n + 6, 1e17);
        build(b, 1, 1, n);
    }
    void build(int b[], int i, int l, int r) {
        if (l == r) {
            sumB[i] = b[l];
            mini[i] = 0 ;
            maxi[i] = 0 ;
            return;
        }
        int m = (l + r) >> 1;
        build(b, i << 1, l, m); build(b, i << 1 | 1, m + 1, r);
        sumB[i] = sumB[i << 1] + sumB[i << 1 | 1];
    }
    void pushdown(int i) {
        for(int j=i<<1; j<=(i<<1|1); ++j) {
            sum[j] += lz[i] * sumB[j];
            maxi[j] += lz[i] ;
            mini[j] += lz[i] ;
            lz[j] += lz[i];
        }
        lz[i] = 0;
    }
    void upd(int i, int l, int r, int u, int v, ll delta) {
        if (l > r || u > v || l > v || r < u) return;
        if (l >= u && r <= v) {
            sum[i] += delta * sumB[i];
            maxi[i] += delta ;
            mini[i] += delta ;
            lz[i] += delta;
            return;
        }
        pushdown(i);
        int m = (l + r) >> 1;
        upd(i << 1, l, m, u, v, delta); upd(i << 1 | 1, m + 1, r, u, v, delta);
        sum[i] = sum[i << 1] + sum[i << 1 | 1];
        maxi[i] = max(maxi[i<<1] , maxi[i<<1 | 1]) ;
        mini[i] = min(mini[i<<1] , mini[i<<1 | 1]) ;
    }
    void upd(int u, int v, ll delta) {
        upd(1, 1, n, u, v, delta);
    }
    ll f(ll x , ll y , ll tp)
    {
        if(tp==1) return x+y ;
        if(tp==2) return min(x , y) ;
        if(tp==3) return max(x , y) ;
    }
    ll id(int tp)
    {
        if(tp==1) return 0 ;
        if(tp==2) return 1e17 ;
        if(tp==3) return -1e17 ;
    }
    ll get(int i, int l, int r, int u, int v , int tp) {
        if (l > r || u > v || l > v || r < u) return id(tp);
        if (l >= u && r <= v) return(tp == 1 ? sum[i] : tp==2 ? mini[i] : maxi[i]);
        pushdown(i);
        int m = (l + r) >> 1;
        return f(get(i << 1, l, m, u, v , tp) , get(i << 1 | 1, m + 1, r, u, v , tp) , tp);
    }
    ll get(int u, int v , int tp = 1) {
        return get(1, 1, n, u, v , tp);
    }

};

int a[N] , b[N] ;

segmentTree st ;
int n , q ;

int getlast(int node , int l , int r , int x)
{
    if(l==r) return l ;
    int md = (l+r)/2 ;
    if(x>=st.mini[2*node+1]) return getlast(2*node+1 , md+1 , r , x) ;
    else return getlast(2*node , l , md , x) ;
}


int getlast(int x)
{
    if(st.mini[1]>x) return 0 ;
    return getlast(1 , 1 , n , x) ;
}

int getfirst(int node , int l , int r , int x)
{
    if(l==r) return l ;
    int md = (l+r)/2 ;
    if(st.maxi[2*node]>=x) return getfirst(2*node , l , md , x) ;
    else return getfirst(2*node+1 , md+1 , r , x) ;
}

int getfirst(int x)
{
    if(st.maxi[1]<x) return n+1 ;
    return getfirst(1 , 1 , n , x) ;
}




int main()
{
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
    cin>>n>>q ;
    for(int i = 1 ; i<=n ; i++){
        cin>>a[i] ;
        b[i] = 1 ;
    }
    st.init(n , b) ;
    sort(a+1 , a+n+1) ;
    for(int i = 1 ; i<=n ; i++){
        st.upd(i , i ,a[i]) ;
    }

//    int m ; cin>>m ;
//    while(m--){
//        int a,  b ; cin>>a>>b ;
//        cout<<getfirst(a)<<' '<<getlast(b)<<endl;
//    }
    while(q--){

        char c ; cin>>c ;
        if(c=='F'){

            int c , h ; cin>>c>>h ;
            int l = getfirst(h) ;
            c = min(c , n - l+1) ;
            int r = min(n , l+c-1) ;
            int x = st.get(r , r) ;
            int lr = getlast(x-1) ;
            int rr = getlast(x) ;
            int lefties = max(0 , lr - l+1) ;
            int rl = (rr - (c - lefties) +1) ;
            // upd [l , lr] , upd[rl , rr]
            if(l<=lr){
                st.upd(l , lr , 1) ;
            }
            if(rl<=rr){
                st.upd(rl , rr , 1) ;
            }

        }
        else{
            int a , b ; cin>>a>>b ;
            cout<<getlast(b) - getfirst(a)+1<<endl;
        }
//        for(int i = 1 ; i<=n ; i++){
//            cout<<st.get(i , i)<<' ';
//        }
//        cout<<endl;
    }

}

Compilation message (stderr)

grow.cpp: In member function 'long long int segmentTree::id(int)':
grow.cpp:72:5: warning: control reaches end of non-void function [-Wreturn-type]
   72 |     }
      |     ^
grow.cpp: In member function 'long long int segmentTree::f(long long int, long long int, long long int)':
grow.cpp:66:5: warning: control reaches end of non-void function [-Wreturn-type]
   66 |     }
      |     ^

• 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