Submission #1255294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255294		MisterReaper	Growing Trees (BOI11_grow)	C++17	0 / 100	67 ms	24388 KiB

grow

// File R.cpp created on 08.08.2025 at 20:58:44
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif


constexpr int max_N = int(1E5) + 5;

int N, Q;
int A[max_N];
struct node {
    int mn, mx, lz;
    node() : mn(0), lz(0) {}
    node(int x) : mn(x), mx(x), lz(0) {}
    void modify(int x) {
        mn += x;
        mx += x;
        lz += x;
    }
} tree[max_N << 1];

node operator+ (const node lhs, const node rhs) {
    node res;
    res.mn = std::min(lhs.mn, rhs.mn);
    res.mx = std::max(lhs.mx, rhs.mx);
    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
void build(int v, int l, int r) {
    if (l == r) {
        tree[v] = A[l];
        return;
    }
    def;
    build(lv, l, mid);
    build(rv, mid + 1, r);
    tree[v] = tree[lv] + tree[rv];
}

void push(int v, int l, int r) {
    def;
    tree[lv].modify(tree[v].lz);
    tree[rv].modify(tree[v].lz);
    tree[v].lz = 0;
}

void modify(int v, int l, int r, int ql, int qr, int x) {
    if (ql == l && r == qr) {
        tree[v].modify(x);
        return;
    }
    def;
    push(v, l, r);
    if (qr <= mid) {
        modify(lv, l, mid, ql, qr, x);
    } else if (mid + 1 <= ql) {
        modify(rv, mid + 1, r, ql, qr, x);
    } else {
        modify(lv, l, mid, ql, mid, x);
        modify(rv, mid + 1, r, mid + 1, qr, x);
    }
    tree[v] = tree[lv] + tree[rv];
}

int get(int v, int l, int r, int p) {
    if (l == r) {
        return tree[v].mn;
    }
    def;
    push(v, l, r);
    if (p <= mid) {
        return get(lv, l, mid, p);
    } else {
        return get(rv, mid + 1, r, p);
    }
}

int find_first(int v, int l, int r, int x) {
    if (tree[v].mx < x) {
        return r + 1;
    } else if (l == r) {
        return l;
    }
    def;
    push(v, l, r);
    int y = find_first(lv, l, mid, x);
    if (y == mid + 1) {
        y = find_first(rv, mid + 1, r, x);
    }
    return y;
}

int find_last(int v, int l, int r, int x) {
    if (tree[v].mn > x) {
        return l - 1;
    } else if (l == r) {
        return l;
    }
    def;
    push(v, l, r);
    int y = find_last(rv, mid + 1, r, x);
    if (y == mid) {
        y = find_last(lv, l, mid, x);
    }
    return y;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> Q;

    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::sort(A, A + N);

    build(0, 0, N - 1);

    for (int _ = 0; _ < Q; ++_) {
        char C;
        int X, Y;
        std::cin >> C >> X >> Y;
        if (C == 'F') {
            int L = find_first(0, 0, N - 1, Y);
            if (L + X >= N) {
                modify(0, 0, N - 1, L, N - 1, +1);
            } else {
                int vl = get(0, 0, N - 1, L);
                int vr = get(0, 0, N - 1, L + X - 1);
                if (vl == vr) {
                    int R = find_last(0, 0, N - 1, vl);
                    modify(0, 0, N - 1, R - X + 1, R, +1);
                } else {
                    int R = find_last(0, 0, N - 1, vr - 1);
                    modify(0, 0, N - 1, L, R, +1);
                    int c = R - L + 1;
                    R = find_last(0, 0, N - 1, vr);
                    modify(0, 0, N - 1, R - (Y - X + 1) - c + 1, R, +1);
                }
            }
        } else {
            int L = find_first(0, 0, N - 1, X);
            int R = find_last(0, 0, N - 1, Y);
            std::cout << R - L + 1 << '\n';
        }
    }

    return 0;
}

• 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