oj.uz

답안 #725491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725491 2023-04-17T14:15:48 Z smirichto Growing Trees (BOI11_grow) C++17
100 / 100
 972 ms 17740 KB 
#include <bits/stdc++.h>

using namespace std;

const long long N = 2e5 + 5 ;

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

struct segmentTree {
    ll n;
    vector<ll> sum, lz, sumB , maxi , mini;
    void init(ll _n, ll 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, -2e9);
        mini.assign(4 * n + 6, 2e9);
        build(b, 1, 1, n);
    }
    void build(ll b[], ll i, ll l, ll r) {
        if (l == r) {
            sumB[i] = b[l];
            mini[i] = 0 ;
            maxi[i] = 0 ;
            return;
        }
        ll 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(ll i) {
        for(ll 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(ll i, ll l, ll r, ll u, ll 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);
        ll 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(ll u, ll 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) ;
        return max(x , y) ;
    }
    ll id(ll tp)
    {
        if(tp==1) return 0 ;
        if(tp==2) return 2e9 ;
        return -2e9 ;
    }
    ll get(ll i, ll l, ll r, ll u, ll v , ll 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);
        ll 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 get2(ll node , ll l , ll r , ll idx){
        if(l==r) return sum[node];
        pushdown(node) ;
        ll md = (l+r)/2;
        if(idx<=md) return get2(2*node,l,md,idx);
        return get2(2*node+1,md+1,r,idx);
    }
    ll get(ll u, ll v , ll tp = 1) {
        return get(1, 1, n, u, v , tp);
    }

};

ll a[N] , b[N] ;

segmentTree st ;
ll n , q ;

ll getlast(ll x)
{
    ll l = 1 , r = n , p = 0 ;
    while(l<=r){
        ll md = (l+r)/2 ;
        ll y = st.get2(1 , 1 , n , md) ;
        if(y<=x){
            p = md ;
            l = md+1 ;
        }
        else r = md-1 ;
    }
    return p ;
}
ll getfirst(ll x)
{
    ll l = 1 , r = n , p = n+1 ;
    while(l<=r){
        ll md = (l+r)/2 ;
        ll y = st.get2(1 , 1 , n , md) ;
        if(y>=x){
            p = md ;
            r = md-1 ;
        }
        else l = md+1 ;
    }
    return p ;
}





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

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

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

            ll c , h ; cin>>c>>h ;
            ll l = getfirst(h) ;
            if(l==n+1) continue ;
            c = min(c , n - l+1) ;
            ll r = min(n , l+c-1) ;
            if(r==n){
                st.upd(l , r , 1) ;
                continue ;
            }
            ll x = st.get(r , r) ;
            ll lr = getlast(x-1) ;
            ll rr = getlast(x) ;
            ll lefties = max(0LL , lr - l+1) ;
            ll 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{
            ll a , b ; cin>>a>>b ;
            cout<<getlast(b) - getfirst(a)+1<<endl;
        }
//        for(ll i = 1 ; i<=n ; i++){
//            cout<<st.get(i , i)<<' ';
//        }
//        cout<<endl;
    }

}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 605 ms 15952 KB Output is correct
2 Correct 632 ms 15304 KB Output is correct
3 Correct 452 ms 14456 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 175 ms 1380 KB Output is correct
6 Correct 217 ms 1536 KB Output is correct
7 Correct 17 ms 1208 KB Output is correct
8 Correct 175 ms 1376 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 1828 KB Output is correct
2 Correct 224 ms 1904 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 182 ms 1740 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 2144 KB Output is correct
2 Correct 251 ms 1824 KB Output is correct
3 Correct 27 ms 1492 KB Output is correct
4 Correct 212 ms 1880 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 11724 KB Output is correct
2 Correct 583 ms 12776 KB Output is correct
3 Correct 66 ms 3404 KB Output is correct
4 Correct 376 ms 12612 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 13304 KB Output is correct
2 Correct 592 ms 13952 KB Output is correct
3 Correct 447 ms 12372 KB Output is correct
4 Correct 68 ms 3392 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 630 ms 14356 KB Output is correct
2 Correct 615 ms 15592 KB Output is correct
3 Correct 447 ms 14104 KB Output is correct
4 Correct 64 ms 3428 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 638 ms 15264 KB Output is correct
2 Correct 617 ms 13600 KB Output is correct
3 Correct 116 ms 17532 KB Output is correct
4 Correct 972 ms 15980 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 596 ms 15288 KB Output is correct
2 Correct 620 ms 15580 KB Output is correct
3 Correct 790 ms 17364 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 17740 KB Output is correct