oj.uz

Submission #668115

# Submission time Handle Problem Language Result Execution time Memory
668115 2022-12-02T19:44:59 Z borisAngelov Growing Trees (BOI11_grow) C++11
100 / 100
 881 ms 5392 KB 
#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];

inline 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;
}

inline 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];
}

inline 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 5072 KB Output is correct
2 Correct 679 ms 4816 KB Output is correct
3 Correct 243 ms 4760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 8 ms 420 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 248 ms 832 KB Output is correct
6 Correct 327 ms 912 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 195 ms 832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 1008 KB Output is correct
2 Correct 336 ms 1024 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 228 ms 784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 984 KB Output is correct
2 Correct 358 ms 892 KB Output is correct
3 Correct 38 ms 596 KB Output is correct
4 Correct 310 ms 940 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 2764 KB Output is correct
2 Correct 658 ms 4892 KB Output is correct
3 Correct 83 ms 1440 KB Output is correct
4 Correct 198 ms 4708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 4848 KB Output is correct
2 Correct 634 ms 4864 KB Output is correct
3 Correct 298 ms 4796 KB Output is correct
4 Correct 88 ms 1548 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 4936 KB Output is correct
2 Correct 486 ms 4944 KB Output is correct
3 Correct 253 ms 4684 KB Output is correct
4 Correct 83 ms 1488 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 4848 KB Output is correct
2 Correct 673 ms 4908 KB Output is correct
3 Correct 145 ms 4756 KB Output is correct
4 Correct 535 ms 4856 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 5112 KB Output is correct
2 Correct 676 ms 4976 KB Output is correct
3 Correct 881 ms 4820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 5392 KB Output is correct