oj.uz

Submission #638211

# Submission time Handle Problem Language Result Execution time Memory
638211 2022-09-04T21:44:30 Z finn__ Growing Trees (BOI11_grow) C++17
10 / 100
 261 ms 4304 KB 
#include <bits/stdc++.h>
using namespace std;

struct fenwick_tree
{
    vector<long> tree;
    size_t l;

    fenwick_tree(size_t n)
    {
        l = n;
        tree = vector<long>(1 << (32 - __builtin_clz(n)), 0);
    }

    void update(size_t i, long x)
    {
        i++;
        while (i <= tree.size())
        {
            tree[i - 1] += x;
            i += i & -i;
        }
    }

    long prefix_sum(size_t i)
    {
        i++;
        long x = 0;
        while (i)
        {
            x += tree[i - 1];
            i -= i & -i;
        }
        return x;
    }
};

size_t ftree_lower_bound(fenwick_tree &t, long x)
{
    size_t a = 0, b = t.l - 1;

    while (a < b)
    {
        size_t mid = (a + b) / 2;
        if (t.prefix_sum(mid) < x)
            a = mid + 1;
        else
            b = mid;
    }

    return a;
}

size_t ftree_upper_bound(fenwick_tree &t, long x)
{
    size_t a = 0, b = t.l - 1;

    while (a < b)
    {
        size_t mid = (a + b) / 2;
        if (t.prefix_sum(mid) <= x)
            a = mid + 1;
        else
            b = mid;
    }

    return a;
}

int main()
{
    size_t n, m;
    cin >> n >> m;

    vector<long> seq(n);
    for (long &x : seq)
        cin >> x;

    sort(seq.begin(), seq.end());
    fenwick_tree tree(n);
    tree.update(0, seq[0]);
    for (size_t i = 1; i < n; i++)
        tree.update(i, seq[i] - seq[i - 1]);

    for (size_t i = 0; i < m; i++)
    {
        char t;
        cin >> t;

        switch (t)
        {
        case 'F':
        {
            long c, h;
            cin >> c >> h;
            size_t l = ftree_lower_bound(tree, h);
            size_t r = min(l + c - 1, tree.l - 1);
            if (r == tree.l - 1)
            {
                tree.update(l, 1);
            }
            else
            {
                size_t y = ftree_upper_bound(tree, tree.prefix_sum(r));
                size_t x = ftree_lower_bound(tree, tree.prefix_sum(r)) - 1;
                tree.update(y - (r - x), 1);
                tree.update(y, -1);
                tree.update(l, 1);
                tree.update(x + 1, -1);
            }
            break;
        }
        case 'C':
        {
            long hmin, hmax;
            cin >> hmin >> hmax;

            size_t l = ftree_lower_bound(tree, hmin);
            size_t r = ftree_upper_bound(tree, hmax);
            if (r == tree.l - 1 && l < tree.l - 1)
                r++;
            cout << (r - l) << '\n';
            break;
        }
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 3364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 7 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 1676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 2416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 3040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 2984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 3708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 4304 KB Output is correct