제출 #1213395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213395		orzorzorz	Growing Trees (BOI11_grow)	C++20	0 / 100	66 ms	3140 KiB

grow

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

#define ll long long
const int mxN = 1e5 + 1;

ll bit[mxN + 1], a[mxN + 1], d[mxN + 1];
int n, m;

void upd(int pos, ll val) {
    for (; pos <= mxN; pos += pos & -pos) {
        bit[pos] += val;
    }
}

ll qry(int pos) {
    ll res = 0;
    for (; pos; pos -= pos & -pos) {
        res += bit[pos];
    }
    return res;
}

int f(ll val) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (qry(mid) >= val) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
        upd(i, d[i]);
    }
    for (int i = 0; i < m; i++) {
        char ty;
        cin >> ty;
        if (ty == 'F') {
            int c, h;
            cin >> c >> h;
            int left = f(h);
            if (left == n + 1) continue; // No trees ≥ h
            int right = left + c - 1;
            if (right > n) {
                upd(left, 1);
                upd(n + 1, -1);
            } else {
                upd(left, 1);
                upd(right + 1, -1);
            }
        } else {
            ll x, y;
            cin >> x >> y;
            int l = f(x), r = f(y + 1);
            if (l == n + 1) {
                cout << 0 << "\n";
            } else {
                if (r == n + 1) r--;
                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