제출 #668114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668114		borisAngelov	Growing Trees (BOI11_grow)	C++11	90 / 100	1040 ms	6732 KiB

grow

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1000005;

int n, q;

int a[maxn];

long long tree[4 * maxn];
long long lazy[4 * maxn];

void push_lazy(int node, int l, int r) {
    tree[node] += lazy[node];

    if (l != r) {
        lazy[(node << 1)] += lazy[node];
        lazy[((node << 1) | 1)] += lazy[node];
    }

    lazy[node] = 0;
}

void update(int node, int l, int r, int ql, int qr, int delta) {
    push_lazy(node, l, r);

    if (l > qr || r < ql) return;

    if (ql <= l && r <= qr) {
        lazy[node] += delta;
        push_lazy(node, l, r);
        return;
    }

    int mid = (l + r) >> 1;

    update((node << 1), l, mid, ql, qr, delta);
    update(((node << 1) | 1), mid + 1, r, ql, qr, delta);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long query(int node, int l, int r, int ql, int qr) {
    push_lazy(node, l, r);

    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return tree[node];

    int mid = (l + r) >> 1;

    return query((node << 1), l, mid, ql, qr) + query(((node << 1) | 1), mid + 1, r, ql, qr);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    //for (int i = 1; i <= n; ++i) cout << a[i] << " "; cout << endl;

    for (int i = 1; i <= n; ++i) {
        update(1, 1, n, i, i, a[i]);
    }

    while (q--) {
        char type; cin >> type;

        if (type == 'C') {
            int minh, maxh; cin >> minh >> maxh;

            int l = 1;
            int r = n;

            while (l <= r) {
                int mid = (l + r) >> 1;

                if (query(1, 1, n, mid, mid) >= minh) r = mid - 1;
                else l = mid + 1;
            }

            int lb = l;

            l = 1;
            r = n;

            while (l <= r) {
                int mid = (l + r) >> 1;

                if(query(1, 1, n, mid, mid) <= maxh) l = mid + 1;
                else r = mid - 1;
            }

            int ub = l;

            //cout << "query: " << lb << " " << ub << endl;

            cout << ub - lb << "\n";
        } else {
            int c, minh; cin >> c >> minh;

            int l = 1;
            int r = n;

            while (l <= r) {
                int mid = (l + r) >> 1;

                if (query(1, 1, n, mid, mid) >= minh) r = mid - 1;
                else l = mid + 1;
            }

            if (l == n + 1) {
                continue;
            }

            int start_index = l;
            int end_index = l + c - 1;

            //cout << "start_index = " << start_index << endl;
            //cout << "end_index = " << end_index << endl;

            if (end_index >= n) {
                update(1, 1, n, start_index, n, 1);
                continue;
            }

            int target = query(1, 1, n, end_index, end_index);
            //cout << "target = " << target << endl;

            l = 1;
            r = n;

            while (l <= r) {
                int mid = (l + r) >> 1;

                if (query(1, 1, n, mid, mid) >= target) r = mid - 1;
                else l = mid + 1;
            }

            int firstMeet = l;

            l = 1;
            r = n;

            while (l <= r) {
                int mid = (l + r) >> 1;

                if (query(1, 1, n, mid, mid) >= target + 1) r = mid - 1;
                else l = mid + 1;
            }

            int lastMeet = l - 1;

            //cout << "first Meet = " << firstMeet << endl;
            //cout << "last Meet = " << lastMeet << endl;

            //cout << "update " << start_index << " " << firstMeet - 1 << endl;

            update(1, 1, n, start_index, firstMeet - 1, 1);

            int remaining_elements = c - (firstMeet - start_index);

            update(1, 1, n, lastMeet - remaining_elements + 1, lastMeet, 1);

            //cout << "update " << lastMeet - remaining_elements + 1 << " " << lastMeet << endl;
        }

        //cout << "after perform: " << endl;
        //for (int i = 1; i <= n; ++i) cout << query(1, 1, n, i, i) << " ";
        //cout << endl << "--------------------------------" << endl;
    }

    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: 0 / 10
• Subtask 10: 10 / 10