oj.uz

답안 #725439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725439 2023-04-17T12:43:22 Z smirichto Growing Trees (BOI11_grow) C++17
90 / 100
 1000 ms 12204 KB 
#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;
    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);
        build(b, 1, 1, n);
    }
    void build(int b[], int i, int l, int r) {
        if (l == r) {
            sumB[i] = b[l];
            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];
            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];
            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];
    }
    void upd(int u, int v, ll delta) {
        upd(1, 1, n, u, v, delta);
    }
    ll get(int i, int l, int r, int u, int v) {
        if (l > r || u > v || l > v || r < u) return 0;
        if (l >= u && r <= v) return sum[i];
        pushdown(i);
        int m = (l + r) >> 1;
        return get(i << 1, l, m, u, v) + get(i << 1 | 1, m + 1, r, u, v);
    }
    ll get(int u, int v) {
        return get(1, 1, n, u, v);
    }
};

int a[N] , b[N] ;

segmentTree st ;
int n , q ;

int getlast(int x)
{
    int l = 1 , r = n , p = 0 ;
    while(l<=r){
        int md = (l+r)/2 ;
        int y = st.get(md , md) ;
        if(y<=x){
            p = md ;
            l = md+1 ;
        }
        else r = md-1 ;
    }
    return p ;
}
int getfirst(int x)
{
    int l = 1 , r = n , p = n+1 ;
    while(l<=r){
        int md = (l+r)/2 ;
        int y = st.get(md , 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(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]) ;
    }
//    for(int i = 1 ; i<=n ; i++){
//        cout<<st.get(i , i)<<' ';
//    }
//    cout<<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;
    }

}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 632 ms 9400 KB Output is correct
2 Correct 862 ms 10836 KB Output is correct
3 Correct 936 ms 10388 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 11 ms 468 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 303 ms 1796 KB Output is correct
6 Correct 378 ms 2124 KB Output is correct
7 Correct 26 ms 848 KB Output is correct
8 Correct 231 ms 1576 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 1472 KB Output is correct
2 Correct 358 ms 2472 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 282 ms 1996 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 1416 KB Output is correct
2 Correct 420 ms 2380 KB Output is correct
3 Correct 44 ms 1112 KB Output is correct
4 Correct 366 ms 2428 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 7140 KB Output is correct
2 Correct 881 ms 9044 KB Output is correct
3 Correct 128 ms 2556 KB Output is correct
4 Correct 736 ms 8988 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 727 ms 8072 KB Output is correct
2 Correct 857 ms 9640 KB Output is correct
3 Correct 883 ms 9248 KB Output is correct
4 Correct 102 ms 2504 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 633 ms 8664 KB Output is correct
2 Correct 694 ms 10592 KB Output is correct
3 Correct 930 ms 10116 KB Output is correct
4 Correct 106 ms 2424 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 913 ms 9284 KB Output is correct
2 Correct 850 ms 9476 KB Output is correct
3 Correct 154 ms 11292 KB Output is correct
4 Correct 744 ms 10796 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 781 ms 9368 KB Output is correct
2 Correct 890 ms 10900 KB Output is correct
3 Execution timed out 1081 ms 12204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

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