Submission #702396

#	Time	Username	Problem	Language	Result	Execution time	Memory
702396		thimote75	Growing Trees (BOI11_grow)	C++14	100 / 100	464 ms	9104 KiB

grow

#include <bits/stdc++.h>

using namespace std;

#define num long long

struct SGD {
    num sum  = 0;
    num size = 1;

    num __l_value = 0;
};

struct SegTree {
    vector<SGD> tree;

    int size, start, height;

    SegTree (int ps) {
        size   = ps;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);

        for (int h = height - 1; h >= 0; h --) {
            int s = 1 << h;

            for (int i = 0; i < s; i ++)
                tree[i + s].size = 2 * tree[(i + s) * 2].size;
        }
    }

    void _update (int index) {
        if (index == 0) return ;
        if (index >= start) {
            _update(index >> 1);

            tree[index].sum += tree[index].__l_value * tree[index].size;
            tree[index].__l_value = 0;
            return ;
        }

        _update(index >> 1);
        int n0 = index << 1;
        int n1 = n0 + 1;

        tree[n0].__l_value += tree[index].__l_value;
        tree[n1].__l_value += tree[index].__l_value;
        tree[index].sum += tree[index].__l_value * tree[index].size;

        tree[index].__l_value = 0;
    }
    num _value (int index) {
        index += start;
        _update(index);

        return tree[index].sum;
    }
    void _modify (int index, int delta) {
        _update(index);
        tree[index].__l_value += delta;
    }
    void modify (int left, int right, int delta) {
        left  += start;
        right += start;

        while (left < right) {
            if ((left  & 1) == 1) _modify(left,  delta);
            if ((right & 1) == 0) _modify(right, delta);

            left  = (left  + 1) >> 1;
            right = (right - 1) >> 1;
        }

        if (left == right) _modify(left, delta);
    }

    // Find first value such that S[b] > value
    int lower_bound (num value) {
        int a = -1;
        int b = size;

        while (b - a > 1) {
            int c = (a + b) >> 1;
            if (_value(c) > value) b = c;
            else a = c;
        }

        return b;
    }
    int upper_bound (num value) {
        return lower_bound(value - 1); // x >= A <=> x > A - 1
    }

    int count (int min, int max) {
        return lower_bound(max) - upper_bound(min);
    }

    void update_1 (int min_v, int count) {
        int start = upper_bound(min_v);
        int end   = start + count - 1;

        if (end >= size) end = size - 1;

        if (end + 1 != size && _value(end) == _value(end + 1)) {
            int e_partial = end;
            end = upper_bound(_value(e_partial));

            int c_partial = e_partial - end + 1;
            end --;

            int s_partial = lower_bound(_value(e_partial));

            modify(s_partial - c_partial, s_partial - 1, 1);
        }

        modify(start, end, 1);
    }

    void show () {
        for (int x = 0; x < size; x ++)
            cout << _value(x) << " ";
        cout << endl;
    }
};

int main () {
    int nbNodes, nbQuery;
    scanf("%d%d", &nbNodes, &nbQuery);

    SegTree tree(nbNodes);

    vector <int> val(nbNodes);
    for (int idNode = 0; idNode < nbNodes; idNode ++) scanf("%d", &val[idNode]);
    sort(val.begin(), val.end());
    for (int idNode = 0; idNode < nbNodes; idNode ++)
        tree.modify(idNode, idNode, val[idNode]);

    for (int idQ = 0; idQ < nbQuery; idQ ++) {
        string bf;
        cin >> bf;

        if (bf[0] == 'F') {
            int c, h;
            scanf("%d%d", &c, &h);

            tree.update_1(h, c);
        } else {
            int m0, m1;
            scanf("%d%d", &m0, &m1);

            printf("%d\n", tree.count(m0, m1));
        }
    }
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d%d", &nbNodes, &nbQuery);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:136:60: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     for (int idNode = 0; idNode < nbNodes; idNode ++) scanf("%d", &val[idNode]);
      |                                                       ~~~~~^~~~~~~~~~~~~~~~~~~~
grow.cpp:147:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |             scanf("%d%d", &c, &h);
      |             ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:152:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |             scanf("%d%d", &m0, &m1);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10