Submission #867439

#	Time	Username	Problem	Language	Result	Execution time	Memory
867439		TahirAliyev	Growing Trees (BOI11_grow)	C++17	100 / 100	210 ms	5196 KiB

grow

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define oo 2e9

const int MAX = 1e5 + 5;
int n, q;
int tree[4 * MAX], lazy[4 * MAX];
vector<int> v;

void build(int node = 1, int l = 1, int r = n + 1){
    if(l == r){
        tree[node] = v[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

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

void update(int node, int l, int r, int ul, int ur){
    relax(node, l, r);
    if(ur < l || r < ul) return;
    if(ul <= l && r <= ur){
        lazy[node]++;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur);
    update(2 * node + 1, mid + 1, r, ul, ur);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int get(int node, int l, int r, int pos){
    relax(node, l, r);
    if(l == r) return tree[node];
    int mid = (l + r) / 2;
    if(pos <= mid){
        return get(2 * node, l, mid, pos);
    }
    else{
        return get(2 * node + 1, mid + 1, r, pos);
    }
}

int lowb(int a){
    int node = 1;
    int l = 1, r = n + 1;
    while(l < r){
        int mid = (l + r) / 2;
        relax(node, l, r);
        relax(2 * node, l, mid);
        relax(2 * node + 1, mid + 1, r);
        if(tree[2 * node] >= a){
            node *= 2;
            r = mid;
        }
        else{
            node = 2 * node + 1;
            l = mid + 1;
        }
    }
    return l;
}

int upb(int a){
    int node = 1;
    int l = 1, r = n + 1;
    while(l < r){
        int mid = (l + r) / 2;
        relax(node, l, r);
        relax(2 * node, l, mid);
        relax(2 * node + 1, mid + 1, r);
        if(tree[2 * node] > a){
            node *= 2;
            r = mid;
        }
        else{
            node = 2 * node + 1;
            l = mid + 1;
        }
    }
    return l;
}

int main(){
    cin >> n >> q;
    v.push_back(0);
    for(int i = 1; i <= n; i++){
        int a; cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    v.push_back(oo);
    build();
    while(q--){
        string s; cin >> s;
        if(s[0] == 'F'){
            int k, s; cin >> k >> s;
            int ul1 = lowb(s);
            if(ul1 + k - 1 > n){
                update(1, 1, n + 1, ul1, n);
                continue;
            }
            int a = get(1, 1, n + 1, ul1 + k - 1);
            int ur1 = lowb(a) - 1;
            int ur2 = upb(a) - 1;
            int ul2 = ur2 - (k - (ur1 - ul1 + 1)) + 1;
            update(1, 1, n + 1, ul1, ur1);
            update(1, 1, n + 1, ul2, ur2);
        }
        else{
            int a, b; cin >> a >> b;
            cout << upb(b) - lowb(a) << '\n';
        }
    }        
}

• 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