oj.uz

답안 #560522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560522 2022-05-11T15:22:55 Z Seb Growing Trees (BOI11_grow) C++17
100 / 100
 178 ms 9156 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

struct Node {
    ll val,lazy;
    Node() : val(0LL), lazy(0LL) {}
};

void push(Node st[], ll nodo, ll ini, ll fin) {
    st[nodo].val += st[nodo].lazy;
    if (ini!=fin) {
        st[nodo*2].lazy += st[nodo].lazy;
        st[nodo*2+1].lazy += st[nodo].lazy;
    }
    st[nodo].lazy = 0;
    return;
}

void set_up(Node st[], ll num[], ll nodo = 1, ll ini = 0, ll fin = n-1) {
    if (ini==fin) {
        st[nodo].val = num[ini];
        return;
    }
    set_up(st,num,nodo*2,ini,(ini+fin)/2);
    set_up(st,num,nodo*2+1,(ini+fin)/2+1,fin);
    st[nodo].val = max(st[nodo*2].val,st[nodo*2+1].val);
    return;
}

ll search_num(Node st[], ll x, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (st[nodo].val < x) return fin+1;
    if (ini==fin) return ini;
    push(st,nodo*2,ini,(ini+fin)/2);
    push(st,nodo*2,(ini+fin)/2+1,fin);
    if (st[nodo*2].val>=x) return search_num(st,x,nodo*2,ini,(ini+fin)/2);
    else return search_num(st,x,nodo*2+1,(ini+fin)/2+1,fin);
}

void update(Node st[], ll l, ll r, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (r<ini || l>fin) return;
    if (l<=ini && fin<=r) {
        st[nodo].lazy++;
        push(st,nodo,ini,fin);
        return;
    }
    update(st,l,r,nodo*2,ini,(ini+fin)/2);
    update(st,l,r,nodo*2+1,(ini+fin)/2+1,fin);
    st[nodo].val = max(st[nodo*2].val,st[nodo*2+1].val);
    return;
}

ll pos(Node st[], ll p, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (ini==fin) return st[nodo].val;
    if (p<=(ini+fin)/2) return pos(st,p,nodo*2,ini,(ini+fin)/2);
    else return pos(st,p,nodo*2+1,(ini+fin)/2+1,fin);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll q,i;
cin>>n>>q;
Node st[4*n];
ll num[n];
for (i=0;i<n;i++) cin>>num[i];
sort(num,num+n);
set_up(st,num);
while (q--) {
    char a;
    ll p,q;
    cin>>a>>p>>q;
    if (a=='F') {
        ll inicio,ultimo,cantidad,aux;
        inicio = search_num(st,q);
        if (inicio+p>=n) update(st,inicio,n-1);
        else {
            aux = pos(st,inicio+p-1);
            ultimo = search_num(st,aux+1)-1;
            cantidad = search_num(st,aux)-inicio;
            if (inicio<=inicio+cantidad-1) update(st,inicio,inicio+cantidad-1);
            update(st,ultimo-(p-cantidad)+1,ultimo);
        }
    }
    else {
        cout<<search_num(st,q+1)-search_num(st,p)<<"\n";
    }
}
return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 6644 KB Output is correct
2 Correct 120 ms 8016 KB Output is correct
3 Correct 52 ms 7756 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 49 ms 1712 KB Output is correct
6 Correct 61 ms 1960 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 38 ms 1396 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 1140 KB Output is correct
2 Correct 59 ms 2116 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 47 ms 1672 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 1236 KB Output is correct
2 Correct 62 ms 2076 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 62 ms 2192 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 5040 KB Output is correct
2 Correct 108 ms 6752 KB Output is correct
3 Correct 16 ms 1928 KB Output is correct
4 Correct 44 ms 6732 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 5636 KB Output is correct
2 Correct 109 ms 7244 KB Output is correct
3 Correct 52 ms 6896 KB Output is correct
4 Correct 15 ms 1876 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 6036 KB Output is correct
2 Correct 83 ms 7816 KB Output is correct
3 Correct 53 ms 7576 KB Output is correct
4 Correct 16 ms 1892 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 6500 KB Output is correct
2 Correct 109 ms 6988 KB Output is correct
3 Correct 31 ms 8020 KB Output is correct
4 Correct 94 ms 7900 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 6536 KB Output is correct
2 Correct 115 ms 8124 KB Output is correct
3 Correct 178 ms 9156 KB Output is correct

Subtask #10
10.0 / 10.0

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