제출 #1198346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198346		Richard_Dyinman	Growing Trees (BOI11_grow)	C++20	100 / 100	129 ms	4420 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define file \
  freopen("barnpainting.in", "r", stdin);\
  freopen("barnpainting.out", "w", stdout)

#define OJudge(in,out) \
      freopen(in, "r", stdin);\
      freopen(out, "w", stdout)


#define FIn   \
  cin.tie(0); \
  cout.tie(0); \
  ios_base::sync_with_stdio(false)

const string IN = "input.txt";
const string OUT = "output.txt";
int  tc;
ll n, m, a, b, k;


struct seg_tree{
    vector<ll>tree ;
    vector<int> lazy;
    int size;
    void init(int n){
        size = 1;
        while(size < n)
            size *=2;
        tree.resize(2*size + 5, 0ll);
        lazy.resize(2*size + 5 , 0ll);
    }

    void set(int idx, ll val, int l, int r, int node){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l + r)/2;
        if(idx <= mid)
            set(idx, val, l , mid, 2*node);
        else
            set(idx, val, mid + 1, r, 2*node + 1);
        tree[node] = max(tree[2*node] , tree[2*node + 1]);
    }


    void set(int idx, ll val){
        set(idx , val, 1, size , 1);
    }

    void push(int l, int r, int node){
        if(r - l){
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }
        tree[node] += lazy[node];
        lazy[node] = 0;
    }

    void add(int l1, int r1, int l, int r, int node){
        push(l , r, node);
        if(r < l1 || l > r1)
            return;
        if(l >= l1 && r <= r1){
            lazy[node]++;
            push(l , r, node);
            return;
        }
        int mid = (l + r)/2;
        add(l1 , r1, l, mid, node*2);
        add(l1 , r1, mid + 1, r, 2*node + 1);
        tree[node] = max(tree[2*node] , tree[2*node + 1]);
    }
    int get_frst(ll h, int l, int r, int node){
        push(l , r , node);
        if(tree[node] < h)
            return n + 1;
        if(l == r){
            return l;
        }
        int mid = (l + r)/2;
        push(l , mid, 2*node);
        if(tree[2*node] >= h)
            return get_frst(h , l , mid, 2*node);
        return get_frst(h , mid + 1, r, 2*node + 1);
    }

    ll get_val(int idx, int l, int r, int node){
        push(l , r, node);
        if(l == r){
            return tree[node];
        }
        int mid = (l + r)/2;
        if(idx <= mid){
            return get_val(idx , l , mid, node*2);
        }
        return get_val(idx, mid + 1, r, 2*node + 1);
    }
    void add(int l, int r){
        if(r < l)
            return;
        add(l , r, 1 , size , 1);
    }

    void apply(ll c, ll h){
        int idx = get_frst(h, 1, size , 1);
        if(idx == n + 1)
            return;
        int lst_idx = min(1ll*((idx + c) - 1) , n);
        ll last = get_val(lst_idx , 1, size, 1);
        int idx2 = get_frst(last , 1 , size , 1);
        int cnt = lst_idx - idx2 + 1;
        add(idx , idx2 - 1);
        idx2 = get_frst(last + 1, 1 , size , 1);
        add(idx2 - cnt , idx2 - 1);
    }

    ll get(ll l, ll r){
        int l1 = get_frst(l , 1 , size, 1);
        int r1 = get_frst(r + 1, 1, size , 1);
        return r1 - l1;
    }
};
int arr[100100];
void solve(){
    cin>>n>>m;
    seg_tree sg;
    sg.init(n);
    for(int i = 1; i <= n; i++){
        cin>>arr[i];
    }
    sort(arr + 1, arr + n + 1);
    for(int i = 1; i <= n; i++){
        sg.set(i , arr[i]);
    }
    while(m--){
        char x;
        cin>>x;
        if(x == 'F'){
            cin>>a>>b;
            sg.apply(a , b);
        }else{
            cin>>a>>b;
            cout<<sg.get(a , b)<<"\n";
        }
    }
}




int main() {
    FIn;
//    file;
// #ifndef ONLINE_JUDGE
//     OJudge(IN.c_str(),OUT.c_str());
// #endif
    bool test = 0;
    if (test)
        cin>>tc;
    else tc = 1;
    for (int i = 1; i<=tc; i++){
        solve();
    }
}

• 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