Submission #1275059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275059		efeg	Growing Trees (BOI11_grow)	C++20	100 / 100	337 ms	4248 KiB

grow

#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(),v.end()

typedef vector<int> vi; 

struct SegTree{
    int n; 
    vi tree,lazy;
    SegTree(int n) : n(n){
        tree.assign(4 * n + 100,0);
        lazy.assign(4 * n + 100,0); 
    }

    void build(int node,int s,int e,vi &a){
        if (s > e) return;
        if (s == e){
            tree[node] = a[s]; 
            return; 
        }
        int m = (s+e) / 2;
        build(node*2,s,m, a);
        build(node*2+1,m+1,e, a); 
    }

    void push(int node,int s,int e){
        if (lazy[node] == 0) return;
        if (s == e) tree[node] += lazy[node]; 
        else {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node]; 
        }
        lazy[node] = 0; 
    }

    int query(int node,int s,int e,int idx){
        push(node,s,e); 
        if (s == e && s == idx) return tree[node]; 
        int m = (s+e) / 2;
        if (idx <= m) return query(node*2,s,m,idx);
        else return query(node*2+1,m+1,e,idx); 
    }
    
    void update(int node,int s,int e,int l,int r){
        push(node,s,e); 
        if (s > e || r < s || e < l) return; 
        if (l <= s && e <= r){
            lazy[node]++;
            push(node,s,e);    
            return; 
        }
        int m = (s+e) / 2;
        update(node*2,s,m,l,r);
        update(node*2+1,m+1,e,l,r); 
    }
    
    
    int find(int val){
        int s = 0,e = n-1,ans = n;
        while (s <= e){
            int m = (s+e) / 2,q = query(1,0,n-1,m); 
            if (val <= q){
                ans = m;
                e = m-1;
            }
            else s = m+1; 
        }
        return ans; 
    }

    int query(int idx) {return query(1,0,n-1,idx);}
    void update(int l,int r){update(1,0,n-1,l,r);} 
};

int n,m;
vi a; 

int32_t main(){
    ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); 
    cin >> n >> m;
    a.assign(n,0);
    for (int i = 0; i < n; i++) cin >> a[i]; 
    sort(all(a)); 

    SegTree tree(n); 
    tree.build(1,0,n-1,a); 

    for (int i = 0; i < m; i++){
        char t; int q1,q2; cin >> t >> q1 >> q2;
        if (t == 'F'){
            int l = tree.find(q2);
            if (l == n) continue;
            int r = min(n-1,l + q1 - 1); 
            int startoflast = tree.find(tree.query(r)); 
            int endoflast = tree.find(tree.query(r) + 1) - 1; 
            if (l < startoflast) tree.update(l,startoflast-1); 
            int siz = r - startoflast + 1; 
            tree.update(endoflast - siz + 1,endoflast);
        }
        else {
            int l = tree.find(q1);
            int r = tree.find(q2+1); 
            cout << r - l << endl; 
        }
    }


}

• 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