Submission #1251536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251536		peteza	Growing Trees (BOI11_grow)	C++20	0 / 100	107 ms	7492 KiB

grow

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

char cmd;
int n, m, a, b;
vector<int> vec;
ll segmn[800005], segmx[800005], laz[800005];

void push(int idx, int len) {
    segmn[idx]+= laz[idx];
    segmx[idx] += laz[idx];
    if(len > 1) {
        laz[idx*2+1] += laz[idx];
        laz[idx*2+2] += laz[idx];
    }
    laz[idx] = 0;
}

void upd(int idx, int l, int r, int tl, int tr, ll val) {
    push(idx, r-l+1);
    if(tr < l || r < tl) return;
    if(tl <= l && r <= tr) {
        laz[idx] = val;
        push(idx, r-l+1);
        return ;
    }
    int mid = (l+r) >> 1;
    upd(idx*2+1, l, mid, tl, tr, val);
    upd(idx*2+2, mid+1, r, tl, tr, val);
    segmn[idx] = min(segmn[idx*2+1], segmn[idx*2+2]);
    segmx[idx] = max(segmx[idx*2+1], segmx[idx*2+2]);
}

int qr(int idx, int l, int r, int tgt) { //returns lower_bound on segm
    push(idx, r-l+1);
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(tgt <= segmx[idx*2+1]) return qr(idx*2+1, l, mid, tgt);
    else return qr(idx*2+2, mid+1, r, tgt);
}

int gn(int idx, int l, int r, int tgt) {
    push(idx, r-l+1);
    if(l == r) return segmn[idx];
    int mid = (l+r) >> 1;
    if(tgt <= mid) return gn(idx*2+1, l, mid, tgt);
    else return gn(idx*2+2, mid+1, r, tgt);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    vec.resize(n);
    for(int &e:vec) cin >> e;
    sort(vec.begin(), vec.end());
    for(int i=0;i<n;i++) {
        upd(0, 1, n+1, i+1, i+1, vec[i]);
    }
    upd(0, 1, n+1, n+1, n+1, 1.5e9);

    while(m--) {
        cin >> cmd >> a >> b;
        if(cmd == 'F') {
            swap(a, b);
            int fst = qr(0, 1, n+1, a);
            if(fst > n) continue;
            if(fst + b -1 >= n) {
                upd(0, 1, n+1, fst, n, 1);
                continue;
            }
            int gtfo = gn(0, 1, n+1, fst + b - 1);
            int fsofgtfo = qr(0, 1, n+1, gtfo);
            int len = fst+b-fsofgtfo;
            int lsofgtfo = qr(0, 1, n+1, gtfo+1) - 1;
            upd(0, 1, n+1, fst, fsofgtfo-1, 1);
            upd(0, 1, n+1, lsofgtfo-len+1, lsofgtfo, 1);
        } else {
            cout << qr(0, 1, n+1, b+1) - qr(0, 1, n+1, a) << '\n';
        }
        //for(int i=1;i<=n;i++) cout << gn(0, 1, n+1, i) << ' '; cout << '\n';
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10