Submission #442477

#	Time	Username	Problem	Language	Result	Execution time	Memory
442477		JovanB	Growing Trees (BOI11_grow)	C++17	100 / 100	248 ms	6080 KiB

grow

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

using ll = long long;
using ld = long double;

const int MAXN = 100000;

struct Segment{
    int mn, mx, lazy;
} seg[4*MAXN+5];

int a[MAXN+5];

void init(int node, int l, int r){
    if(l == r){
        seg[node].mn = seg[node].mx = a[l];
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].mn = seg[node*2].mn;
    seg[node].mx = seg[node*2+1].mx;
}

void propagate(int node, int l, int r){
    seg[node].mn += seg[node].lazy;
    seg[node].mx += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

void upd(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr || tl > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy++;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr);
    upd(node*2+1, mid+1, r, tl, tr);
    seg[node].mn = seg[node*2].mn;
    seg[node].mx = seg[node*2+1].mx;
}

int qpoint(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].mn;
    int mid = (l+r)/2;
    if(x <= mid) return qpoint(node*2, l, mid, x);
    return qpoint(node*2+1, mid+1, r, x);
}

int qmin(int node, int l, int r, int val){
    propagate(node, l, r);
    if(l == r){
        if(seg[node].mn >= val) return l;
        return l+1;
    }
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    if(seg[node*2].mx >= val) return qmin(node*2, l, mid, val);
    return qmin(node*2+1, mid+1, r, val);
}

int qmax(int node, int l, int r, int val){
    propagate(node, l, r);
    if(l == r){
        if(seg[node].mn <= val) return l;
        return l-1;
    }
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    if(seg[node*2+1].mn <= val) return qmax(node*2+1, mid+1, r, val);
    return qmax(node*2, l, mid, val);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    init(1, 1, n);
    while(m--){
        char typ;
        cin >> typ;
        if(typ == 'F'){
            int c, h;
            cin >> c >> h;
            int l = qmin(1, 1, n, h);
            if(l > n) continue;
            int r = l + c - 1;
            if(r > n) r = n;
            int vl = qpoint(1, 1, n, r);
            int dr = qmax(1, 1, n, vl);
            int dl = 1 + qmax(1, 1, n, vl-1);
            int sc = r - dl + 1;
            upd(1, 1, n, l, dl-1);
            upd(1, 1, n, dr-sc+1, dr);
        }
        else{
            int mn, mx;
            cin >> mn >> mx;
            cout << max(0, qmax(1, 1, n, mx) - qmax(1, 1, n, mn-1)) << "\n";
        }
    }
    return 0;
}

• 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