oj.uz

Submission #776192

# Submission time Handle Problem Language Result Execution time Memory
776192 2023-07-07T11:42:59 Z PanosPask Growing Trees (BOI11_grow) C++14
100 / 100
 148 ms 6584 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct SegTree {
    const ll NO_OP = 0;
    const ll NEUTRAL = LLONG_MAX;

    int size;
    int n;
    vector<ll> tree;
    vector<ll> operations;

    void build(vector<int>& a, int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx < a.size())
                tree[x] = a[lx];
            else
                tree[x] = NEUTRAL;
            return;
        }

        int mid = (lx + rx) / 2;

        build(a, 2 * x + 1, lx, mid);
        build(a, 2 * x + 2, mid, rx);

        tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void init(int n, vector<int>& a) {
        size = 1;
        this->n = n;
        while (size < n)
            size *= 2;

        tree.resize(2 * size);
        operations.assign(2 * size, NO_OP);

        build(a, 0, 0, size);
    }

    void propagate(int x) {
        tree[2 * x + 1] += operations[x];
        tree[2 * x + 2] += operations[x];
        operations[2 * x + 1] += operations[x];
        operations[2 * x + 2] += operations[x];

        operations[x] = NO_OP;
    }

    void modify(int l, int r, int v, int x, int lx, int rx) {
        if (lx >= r || l >= rx) {
            return;
        }
        else if (l <= lx && rx <= r) {
            tree[x] += v;
            operations[x] += v;
            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        modify(l, r, v, 2 * x + 1, lx, mid);
        modify(l, r, v, 2 * x + 2, mid, rx);

        tree[x] = max(tree[2 * x + + 1], tree[2 * x + 2]);
    }

    ll get(int i, int x, int lx, int rx) {
        if (lx == rx - 1) {
            return tree[x];
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        if (i < mid)
            return get(i, 2 * x + 1, lx, mid);
        else
            return get(i, 2 * x + 2, mid, rx);
    }

    // Returns the first element more than or equal to v
    int lower_bound(ll v, int x, int lx, int rx) {
        if (tree[x] < v)
            return -1;
        else if (lx == rx - 1)
            return lx;

        propagate(x);

        int mid = (lx + rx) / 2;
        int res = lower_bound(v, 2 * x + 1, lx, mid);
        if (res == -1)
            res = lower_bound(v, 2 * x + 2, mid, rx);

        return res;
    }

    // Count elements with value in [minv, maxv]
    int count_between(int minv, int maxv) {
        int r = lower_bound(maxv + 1, 0, 0, size);
        int l = lower_bound(minv, 0, 0, size);

        return r - l;
    }

    // Increment the shortest num elements with height over minv
    void increment(int minv, int num) {
        // First element to be incremented
        int l = lower_bound(minv, 0, 0, size);
        if (l >= n)
            return;

        // Last element to be incremented
        int r = l + num - 1;
        if (r >= n) {
            modify(l, n, 1, 0, 0, size);
            return;
        }
        ll v = get(r, 0, 0, size);

        // First element equal to a[r]
        int first = lower_bound(v, 0, 0, size);
        // First element equal to (a[r] + 1)
        int last = lower_bound(v + 1, 0, 0, size);

        // The range [l.. f) can be freely incremented
        modify(l, first, 1, 0, 0, size);

        int left_to_inc = num - (first - l);
        // Increment the last elements equal to r
        modify(last - left_to_inc, last, 1, 0, 0, size);

        return;
    }
};

int n, m;
vector<int> a;
SegTree st;

int main(void)
{
    scanf("%d %d", &n, &m);

    a.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a.begin(), a.end());

    st.init(n, a);
    while (m--) {
        char op;
        scanf(" %c", &op);

        if (op == 'F') {
            int c, h;
            scanf("%d %d", &c, &h);

            st.increment(h, c);
        }
        else {
            int l, r;
            scanf("%d %d", &l, &r);

            printf("%d\n", st.count_between(l, r));
        }
    }

    return 0;
}

Compilation message

grow.cpp: In member function 'void SegTree::build(std::vector<int>&, int, int, int)':
grow.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             if (lx < a.size())
      |                 ~~~^~~~~~~~~~
grow.cpp: In function 'int main()':
grow.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
grow.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf(" %c", &op);
      |         ~~~~~^~~~~~~~~~~~
grow.cpp:163:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |             scanf("%d %d", &c, &h);
      |             ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:169:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |             scanf("%d %d", &l, &r);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4924 KB Output is correct
2 Correct 110 ms 6380 KB Output is correct
3 Correct 89 ms 6376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 43 ms 1600 KB Output is correct
6 Correct 58 ms 1852 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 33 ms 1368 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 948 KB Output is correct
2 Correct 53 ms 1992 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 42 ms 1496 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 928 KB Output is correct
2 Correct 54 ms 1888 KB Output is correct
3 Correct 8 ms 696 KB Output is correct
4 Correct 52 ms 1996 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2696 KB Output is correct
2 Correct 117 ms 6064 KB Output is correct
3 Correct 18 ms 1820 KB Output is correct
4 Correct 75 ms 6080 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4744 KB Output is correct
2 Correct 98 ms 6108 KB Output is correct
3 Correct 100 ms 6328 KB Output is correct
4 Correct 15 ms 1748 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4812 KB Output is correct
2 Correct 80 ms 6008 KB Output is correct
3 Correct 101 ms 6368 KB Output is correct
4 Correct 15 ms 1812 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4888 KB Output is correct
2 Correct 109 ms 6068 KB Output is correct
3 Correct 27 ms 5500 KB Output is correct
4 Correct 76 ms 5836 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 4936 KB Output is correct
2 Correct 104 ms 6352 KB Output is correct
3 Correct 148 ms 6584 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5228 KB Output is correct