oj.uz

Submission #946990

# Submission time Handle Problem Language Result Execution time Memory
946990 2024-03-15T09:28:31 Z MisterReaper Growing Trees (BOI11_grow) C++17
100 / 100
 427 ms 5512 KB 
#include <bits/stdc++.h>
using i64 = long long;

constexpr int max_N = 1E5 + 5;

int a[max_N];
int tree[max_N * 4], lazy[max_N * 4];
void build(int node, int l, int r) {
    if(l == r) {
        tree[node] = a[l];
        return;
    }

    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = std::max(tree[node * 2], tree[node * 2 + 1]);
}

void push(int node, int l, int r) {
    tree[node] += lazy[node];
    if(l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int ql, int qr, int v) {
    push(node, l, r);
    if(ql <= l && r <= qr) {
        lazy[node] += v;
        push(node, l, r);
        return;
    } else if(r < ql || qr < l) {
        return;
    }

    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr, v);
    update(node * 2 + 1, mid + 1, r, ql, qr, v);
    tree[node] = std::max(tree[node * 2], tree[node * 2 + 1]);
}

int query(int node, int l, int r, int p) {
    push(node, l, r);
    if(l == r) {
        return tree[node];
    }

    int mid = (l + r) / 2;
    if(p <= mid) {
        return query(node * 2, l, mid, p);
    }
    return query(node * 2 + 1, mid + 1, r, p);
}

void solve() {
    int n, q;
    std::cin >> n >> q;

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

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

    build(1, 1, n);

    auto print = [&]() -> void {
        for(int i = 1; i <= n; i++) {
            std::cerr << query(1, 1, n, i) << " \n"[i == n];
        }
    };
    //print();

    for(int _ = 1; _ <= q; _++) {
        char ty;
        std::cin >> ty;
        if(ty == 'F') {
            int c, h;
            std::cin >> c >> h;

            int found = -1;
            {
                int l = 1, r = n;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(h <= query(1, 1, n, mid)) {
                        found = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }

            if(found == -1) {
                continue;
            } else if(found + c - 1 >= n) {
                update(1, 1, n, found, std::min(n, found + c - 1), 1);
                continue;
            }

            // Oh, now we need left and right increases!
            int last = query(1, 1, n, found + c - 1);
            if(last == h) {
                int foundr = -1;
                {
                    int l = found, r = n;
                    while(l <= r) {
                        int mid = (l + r) / 2;
                        if(query(1, 1, n, mid) <= h) {
                            foundr = mid;
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                }

                assert(foundr != -1);
                update(1, 1, n, foundr - (c - 1), foundr, 1);
                continue;
            }

            int pl = -1;
            {
                int l = found, r = n;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(query(1, 1, n, mid) <= last - 1) {
                        pl = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            if(pl != -1) {
                update(1, 1, n, found, pl, 1);
                c -= pl - found + 1;
            }

            if(c == 0) {
                continue;
            }

            int foundr = -1;
            {
                int l = found, r = n;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(query(1, 1, n, mid) <= last) {
                        foundr = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            assert(foundr != -1);
            update(1, 1, n, foundr - (c - 1), foundr, 1);
        } else {
            int mn, mx;
            std::cin >> mn >> mx;

            int foundl = n + 1;
            {
                int l = 1, r = n;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(mn <= query(1, 1, n, mid)) {
                        foundl = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }

            int foundr = 0;
            {
                int l = 1, r = n;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(query(1, 1, n, mid) <= mx) {
                        foundr = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }

            std::cout << std::max(0, foundr - foundl + 1) << "\n";
        }
        //print();
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Compilation message

grow.cpp: In function 'void solve()':
grow.cpp:70:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   70 |     auto print = [&]() -> void {
      |          ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 4572 KB Output is correct
2 Correct 375 ms 4912 KB Output is correct
3 Correct 105 ms 4944 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 4 ms 2580 KB Output is correct
3 Correct 5 ms 2600 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 140 ms 3408 KB Output is correct
6 Correct 179 ms 3696 KB Output is correct
7 Correct 11 ms 2652 KB Output is correct
8 Correct 94 ms 3212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3652 KB Output is correct
2 Correct 183 ms 3876 KB Output is correct
3 Correct 2 ms 2564 KB Output is correct
4 Correct 118 ms 3508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3924 KB Output is correct
2 Correct 201 ms 3904 KB Output is correct
3 Correct 20 ms 2652 KB Output is correct
4 Correct 178 ms 3780 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 4064 KB Output is correct
2 Correct 344 ms 4696 KB Output is correct
3 Correct 47 ms 3156 KB Output is correct
4 Correct 81 ms 4720 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 4436 KB Output is correct
2 Correct 334 ms 4684 KB Output is correct
3 Correct 107 ms 5456 KB Output is correct
4 Correct 46 ms 3108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 4432 KB Output is correct
2 Correct 218 ms 5204 KB Output is correct
3 Correct 112 ms 4996 KB Output is correct
4 Correct 46 ms 2904 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 5212 KB Output is correct
2 Correct 354 ms 4688 KB Output is correct
3 Correct 53 ms 4140 KB Output is correct
4 Correct 197 ms 4716 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 4688 KB Output is correct
2 Correct 396 ms 4864 KB Output is correct
3 Correct 427 ms 5200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 5512 KB Output is correct