oj.uz

답안 #668114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668114 2022-12-02T19:43:52 Z borisAngelov Growing Trees (BOI11_grow) C++11
90 / 100
 1000 ms 6732 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) {
        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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 5020 KB Output is correct
2 Correct 737 ms 6584 KB Output is correct
3 Correct 276 ms 6400 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 12 ms 468 KB Output is correct
3 Correct 12 ms 464 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 302 ms 1732 KB Output is correct
6 Correct 388 ms 1868 KB Output is correct
7 Correct 22 ms 596 KB Output is correct
8 Correct 257 ms 1400 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 892 KB Output is correct
2 Correct 380 ms 2032 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 321 ms 1484 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 992 KB Output is correct
2 Correct 430 ms 1912 KB Output is correct
3 Correct 48 ms 844 KB Output is correct
4 Correct 381 ms 2024 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 575 ms 2744 KB Output is correct
2 Correct 713 ms 6100 KB Output is correct
3 Correct 103 ms 1840 KB Output is correct
4 Correct 220 ms 6012 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 639 ms 4940 KB Output is correct
2 Correct 702 ms 6284 KB Output is correct
3 Correct 276 ms 6344 KB Output is correct
4 Correct 98 ms 1780 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 617 ms 5000 KB Output is correct
2 Correct 556 ms 6128 KB Output is correct
3 Correct 280 ms 6348 KB Output is correct
4 Correct 98 ms 1812 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 754 ms 4952 KB Output is correct
2 Correct 733 ms 6316 KB Output is correct
3 Correct 120 ms 5532 KB Output is correct
4 Correct 643 ms 6060 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 5028 KB Output is correct
2 Correct 774 ms 6580 KB Output is correct
3 Execution timed out 1040 ms 6732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 667 ms 5324 KB Output is correct