oj.uz

Submission #889920

# Submission time Handle Problem Language Result Execution time Memory
889920 2023-12-20T09:46:25 Z chanhchuong123 Growing Trees (BOI11_grow) C++14
100 / 100
 53 ms 3496 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

const int MAX = 100010;
int nArr;
int nQuery;
int h[MAX];
int bit[MAX];

void update(int id, int delta) {
    for (; id <= nArr; id += id & -id)
        bit[id] += delta;
}

void update(int l, int r, int delta) {
    update(l, +delta);
    update(r + 1, -delta);
}

int getHigh(int id) {
    int res = 0;
    for (; id > 0; id -= id & -id)
        res += bit[id];
    return  res;
}

int getFirst(int high) { // find first pos that h[pos] >= high
    int pos = 0;
    for (int j = 16; j >= 0; --j) {
        if (pos + (1 << j) > nArr) continue;
        if (bit[pos + (1 << j)] < high) {
            pos += 1 << j;
            high -= bit[pos];
        }
    }
    return pos + 1;
}

int getLast(int high) { // find last pos that h[pos] <= high
    int pos = 0;
    for (int j = 16; j >= 0; --j) {
        if (pos + (1 << j) > nArr) continue;
        if (bit[pos + (1 << j)] <= high) {
            pos += 1 << j;
            high -= bit[pos];
        }
    }
    return pos;
}

void process(void) {
    cin >> nArr >> nQuery; for (int i = 1; i <= nArr; ++i) cin >> h[i];
    sort(h + 1, h + 1 + nArr);

    for (int i = 1; i <= nArr; ++i) {
        update(i, h[i] - h[i - 1]);
    }
    while (nQuery--) {
        char o; int l, r; cin >> o >> l >> r;

        if (o == 'F') {
            int L = getFirst(r), R = min(nArr, L + l - 1);
            if (L <= nArr) {
                if (R == nArr) update(L, +1);
                else {
                    int maxHigh = getHigh(R), lastL = getFirst(maxHigh), lastR = getLast(maxHigh);
                    update(L, lastL - 1, +1); l -= lastL - L;
                    update(lastR - l + 1, lastR, +1);
                }
            }
            continue;
        }

        cout << max(0, getLast(r) - getFirst(l) + 1) << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    process();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2332 KB Output is correct
2 Correct 50 ms 2640 KB Output is correct
3 Correct 27 ms 2896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 26 ms 1544 KB Output is correct
6 Correct 28 ms 1628 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 15 ms 1236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1628 KB Output is correct
2 Correct 29 ms 1880 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 18 ms 1372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1884 KB Output is correct
2 Correct 32 ms 1636 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 29 ms 1876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2128 KB Output is correct
2 Correct 45 ms 2388 KB Output is correct
3 Correct 9 ms 856 KB Output is correct
4 Correct 22 ms 2400 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2132 KB Output is correct
2 Correct 45 ms 2404 KB Output is correct
3 Correct 23 ms 2516 KB Output is correct
4 Correct 9 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2124 KB Output is correct
2 Correct 31 ms 2396 KB Output is correct
3 Correct 24 ms 2648 KB Output is correct
4 Correct 9 ms 860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2652 KB Output is correct
2 Correct 47 ms 2340 KB Output is correct
3 Correct 18 ms 1884 KB Output is correct
4 Correct 29 ms 2132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2480 KB Output is correct
2 Correct 50 ms 2828 KB Output is correct
3 Correct 49 ms 2896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3496 KB Output is correct