oj.uz

Submission #668113

# Submission time Handle Problem Language Result Execution time Memory
668113 2022-12-02T19:31:55 Z borisAngelov Growing Trees (BOI11_grow) C++11
0 / 100
 822 ms 7152 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];

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) {
        tree[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 << 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;
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 6076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 3824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 422 ms 5708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 5800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 822 ms 6624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 496 ms 6072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 668 ms 7152 KB Output isn't correct
2 Halted 0 ms 0 KB -