oj.uz

Submission #819866

# Submission time Handle Problem Language Result Execution time Memory
819866 2023-08-10T14:36:00 Z finn__ Radio Towers (IOI22_towers) C++17
17 / 100
 903 ms 70136 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

template <typename T, size_t L>
struct max_segtree
{
    T t[L << 1];

    max_segtree() { fill(t, t + (L << 1), numeric_limits<T>::min() / 4); }

    void update(size_t i, T x)
    {
        i += L;
        t[i] = max(t[i], x);
        while (i >>= 1)
            t[i] = max(t[i << 1], t[i << 1 | 1]);
    }

    T range_max(size_t i, size_t j)
    {
        i += L, j += L;
        T x = numeric_limits<T>::min() / 4;

        while (i <= j)
        {
            if (i & 1)
                x = max(x, t[i++]);
            if (!(j & 1))
                x = max(x, t[j--]);
            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

template <typename T, size_t L>
struct min_segtree
{
    T t[L << 1];

    min_segtree() { fill(t, t + (L << 1), numeric_limits<T>::max() / 4); }

    void update(size_t i, T x)
    {
        i += L;
        t[i] = min(t[i], x);
        while (i >>= 1)
            t[i] = min(t[i << 1], t[i << 1 | 1]);
    }

    T range_min(size_t i, size_t j)
    {
        i += L, j += L;
        T x = numeric_limits<T>::max() / 4;

        while (i <= j)
        {
            if (i & 1)
                x = min(x, t[i++]);
            if (!(j & 1))
                x = min(x, t[j--]);
            i >>= 1;
            j >>= 1;
        }

        return x;
    }

    size_t min_index_r(size_t i, size_t j, T x, size_t k = 1, size_t a = 0, size_t b = L - 1)
    {
        if (b < i || a > j)
            return SIZE_MAX;
        if (i <= a && b <= j)
        {
            if (t[k] != x)
                return SIZE_MAX;

            while (a != b)
            {
                if (t[k << 1] == x)
                    k = k << 1, b = (a + b) >> 1;
                else
                    k = k << 1 | 1, a = ((a + b) >> 1) + 1;
            }

            return a;
        }

        size_t y = min_index_r(i, j, x, k << 1, a, (a + b) >> 1);
        if (y != SIZE_MAX)
            return y;
        return min_index_r(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
    }

    size_t min_index(size_t i, size_t j)
    {
        return min_index_r(i, j, range_min(i, j));
    }
};

template <typename T, size_t L>
struct left_diff_segtree
{
    struct node
    {
        T diff, max_val, min_val;
        node() { diff = numeric_limits<T>::min() / 4, max_val = numeric_limits<T>::min() / 4, min_val = numeric_limits<T>::max() / 4; }
        node(T diff, T max_val, T min_val) { this->diff = diff, this->max_val = max_val, this->min_val = min_val; }
    };

    node t[L << 1];

    node combine(node a, node b)
    {
        return node(max(a.diff, max(b.diff, b.max_val - a.min_val)),
                    max(a.max_val, b.max_val),
                    min(a.min_val, b.min_val));
    }

    void update(size_t i, T x)
    {
        i += L;
        t[i].diff = 0;
        t[i].min_val = t[i].max_val = x;
        while (i >>= 1)
            t[i] = combine(t[i << 1], t[i << 1 | 1]);
    }

    T max_diff(size_t i, size_t j)
    {
        i += L, j += L;
        node x(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4),
            y(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4);

        while (i <= j)
        {
            if (i & 1)
                x = combine(x, t[i++]);
            if (!(j & 1))
                y = combine(t[j--], y);
            i >>= 1;
            j >>= 1;
        }

        return combine(x, y).diff;
    }
};

template <typename T, size_t L>
struct right_diff_segtree
{
    struct node
    {
        T diff, max_val, min_val;
        node() { diff = numeric_limits<T>::min() / 4, max_val = numeric_limits<T>::min() / 4, min_val = numeric_limits<T>::max() / 4; }
        node(T diff, T max_val, T min_val) { this->diff = diff, this->max_val = max_val, this->min_val = min_val; }
    };

    node t[L << 1];

    node combine(node a, node b)
    {
        return node(max(a.diff, max(b.diff, a.max_val - b.min_val)),
                    max(a.max_val, b.max_val),
                    min(a.min_val, b.min_val));
    }

    void update(size_t i, T x)
    {
        i += L;
        t[i].diff = 0;
        t[i].min_val = t[i].max_val = x;
        while (i >>= 1)
            t[i] = combine(t[i << 1], t[i << 1 | 1]);
    }

    T max_diff(size_t i, size_t j)
    {
        i += L, j += L;
        node x(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4),
            y(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4);

        while (i <= j)
        {
            if (i & 1)
                x = combine(x, t[i++]);
            if (!(j & 1))
                y = combine(t[j--], y);
            i >>= 1;
            j >>= 1;
        }

        return combine(x, y).diff;
    }
};

struct node
{
    uint32_t l, r, s;
};

constexpr size_t N = 100000, M = 4000000, L = 1 << 17;

node tree[M];
uint32_t roots[N];
vector<int64_t> delta_coords;
size_t n, left_greater[N], left_smaller[N], right_greater[N], right_smaller[N], num_nodes;
int64_t h[N];

max_segtree<int64_t, L> hmax;
min_segtree<int64_t, L> hmin;
left_diff_segtree<int64_t, L> ltree;
right_diff_segtree<int64_t, L> rtree;

uint32_t incr(size_t i, uint32_t x, size_t k, size_t a = 0, size_t b = L - 1)
{
    uint32_t new_node = num_nodes++;
    if (a == b)
    {
        tree[new_node].s = tree[k].s + x;
        return new_node;
    }

    if (i <= (a + b) >> 1)
    {
        tree[new_node].r = tree[k].r;
        tree[new_node].l = incr(i, x, tree[k].l, a, (a + b) >> 1);
    }
    else
    {
        tree[new_node].l = tree[k].l;
        tree[new_node].r = incr(i, x, tree[k].r, ((a + b) >> 1) + 1, b);
    }

    tree[new_node].s = tree[tree[new_node].l].s + tree[tree[new_node].r].s;
    return new_node;
}

uint32_t range_sum(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
    if (b < i || a > j)
        return 0;
    if (i <= a && b <= j)
        return tree[k].s;
    return range_sum(i, j, tree[k].l, a, (a + b) >> 1) +
           range_sum(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
}

size_t leftmost_nonzero(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
    if (b < i || a > j)
        return SIZE_MAX;
    if (i <= a && b <= j)
    {
        if (!tree[k].s)
            return SIZE_MAX;
        while (a != b)
        {
            if (tree[tree[k].l].s)
                k = tree[k].l, b = (a + b) >> 1;
            else
                k = tree[k].r, a = ((a + b) >> 1) + 1;
        }
        return a;
    }

    size_t y = leftmost_nonzero(i, j, tree[k].l, a, (a + b) >> 1);
    if (y != SIZE_MAX)
        return y;
    return leftmost_nonzero(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
}

size_t rightmost_nonzero(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
    if (b < i || a > j)
        return SIZE_MAX;
    if (i <= a && b <= j)
    {
        if (!tree[k].s)
            return SIZE_MAX;
        while (a != b)
        {
            if (tree[tree[k].r].s)
                k = tree[k].r, a = ((a + b) >> 1) + 1;
            else
                k = tree[k].l, b = (a + b) >> 1;
        }
        return a;
    }

    size_t y = rightmost_nonzero(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
    if (y != SIZE_MAX)
        return y;
    return rightmost_nonzero(i, j, tree[k].l, a, (a + b) >> 1);
}

uint32_t get_root(int64_t delta)
{
    return roots[upper_bound(delta_coords.begin(), delta_coords.end(), delta, greater<int64_t>()) - delta_coords.begin() - 1];
}

void init(int n_, vector<int> h_)
{
    n = n_;
    for (size_t i = 0; i < n; ++i)
        h[i] = h_[i];
    {
        stack<size_t> s;

        for (size_t i = 0; i < n; ++i)
        {
            while (!s.empty() && h[s.top()] < h[i])
                s.pop();
            left_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
            s.push(i);
        }

        while (!s.empty())
            s.pop();

        for (size_t i = 0; i < n; ++i)
        {
            while (!s.empty() && h[s.top()] > h[i])
                s.pop();
            left_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
            s.push(i);
        }

        while (!s.empty())
            s.pop();

        for (size_t i = n - 1; i < n; --i)
        {
            while (!s.empty() && h[s.top()] < h[i])
                s.pop();
            right_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
            s.push(i);
        }

        while (!s.empty())
            s.pop();

        for (size_t i = n - 1; i < n; --i)
        {
            while (!s.empty() && h[s.top()] > h[i])
                s.pop();
            right_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
            s.push(i);
        }
    }

    for (size_t i = 0; i < n; ++i)
    {
        hmax.update(i, h[i]), hmin.update(i, h[i]);
        ltree.update(i, h[i]);
        rtree.update(i, h[i]);
    }

    vector<pair<int64_t, size_t>> delta;
    for (size_t i = 0; i < n; ++i)
    {
        int64_t d = INT64_MAX;
        if (left_smaller[i] != SIZE_MAX)
            d = min(d, hmax.range_max(left_smaller[i] + 1, i - 1));
        if (right_smaller[i] != SIZE_MAX)
            d = min(d, hmax.range_max(i + 1, right_smaller[i] - 1));
        if (left_smaller[i] == SIZE_MAX && right_smaller[i] == SIZE_MAX)
            delta.emplace_back(INT64_MAX, i);
        else if (d != INT64_MIN)
            delta.emplace_back((d - h[i]), i);
    }
    sort(delta.begin(), delta.end(), greater<pair<int64_t, size_t>>());

    uint32_t curr_root = 1;
    for (size_t i = L - 1; i; --i)
        tree[i].l = i << 1, tree[i].r = i << 1 | 1;
    num_nodes = L << 1;

    for (size_t i = 0, k = 0; i < delta.size();)
    {
        size_t j = i;
        while (j < delta.size() && delta[j].first == delta[i].first)
            curr_root = incr(delta[j].second, 1, curr_root), ++j;
        roots[k] = curr_root;
        delta_coords.push_back(delta[i].first);
        i = j;
        ++k;
    }
}

int max_towers(int l, int r, int d)
{
    uint32_t rt = get_root(d);
    uint32_t y = range_sum(l, r, rt);
    if (!y)
    {
        size_t smallest = hmin.min_index(l, r);

        return 1 + ((smallest != l && ltree.max_diff(l, smallest - 1) >= d) ||
                    (smallest != r && rtree.max_diff(smallest + 1, r) >= d));
    }
    else
    {
        size_t u = leftmost_nonzero(l, r, rt),
               v = rightmost_nonzero(l, r, rt);
        return y + (u != l && ltree.max_diff(l, u - 1) >= d) +
               (v != r && rtree.max_diff(v + 1, r) >= d);
    }
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:402:31: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  402 |         return 1 + ((smallest != l && ltree.max_diff(l, smallest - 1) >= d) ||
      |                      ~~~~~~~~~^~~~
towers.cpp:403:31: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  403 |                     (smallest != r && rtree.max_diff(smallest + 1, r) >= d));
      |                      ~~~~~~~~~^~~~
towers.cpp:409:23: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  409 |         return y + (u != l && ltree.max_diff(l, u - 1) >= d) +
      |                     ~~^~~~
towers.cpp:410:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  410 |                (v != r && rtree.max_diff(v + 1, r) >= d);
      |                 ~~^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 70136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18384 KB Output is correct
2 Correct 9 ms 18896 KB Output is correct
3 Correct 8 ms 18896 KB Output is correct
4 Correct 8 ms 18896 KB Output is correct
5 Correct 9 ms 18896 KB Output is correct
6 Correct 11 ms 18884 KB Output is correct
7 Correct 10 ms 18896 KB Output is correct
8 Correct 8 ms 18896 KB Output is correct
9 Incorrect 8 ms 18896 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18384 KB Output is correct
2 Correct 9 ms 18896 KB Output is correct
3 Correct 8 ms 18896 KB Output is correct
4 Correct 8 ms 18896 KB Output is correct
5 Correct 9 ms 18896 KB Output is correct
6 Correct 11 ms 18884 KB Output is correct
7 Correct 10 ms 18896 KB Output is correct
8 Correct 8 ms 18896 KB Output is correct
9 Incorrect 8 ms 18896 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 47656 KB 74909th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 25300 KB Output is correct
2 Correct 850 ms 47784 KB Output is correct
3 Correct 884 ms 47768 KB Output is correct
4 Correct 853 ms 47752 KB Output is correct
5 Correct 749 ms 47772 KB Output is correct
6 Correct 903 ms 47756 KB Output is correct
7 Correct 704 ms 47800 KB Output is correct
8 Correct 776 ms 47948 KB Output is correct
9 Correct 788 ms 48088 KB Output is correct
10 Correct 765 ms 47792 KB Output is correct
11 Correct 736 ms 48024 KB Output is correct
12 Correct 95 ms 47828 KB Output is correct
13 Correct 85 ms 47844 KB Output is correct
14 Correct 82 ms 47756 KB Output is correct
15 Correct 74 ms 48064 KB Output is correct
16 Correct 72 ms 47928 KB Output is correct
17 Correct 81 ms 46840 KB Output is correct
18 Correct 94 ms 48004 KB Output is correct
19 Correct 83 ms 47812 KB Output is correct
20 Correct 88 ms 47812 KB Output is correct
21 Correct 81 ms 47812 KB Output is correct
22 Correct 81 ms 47756 KB Output is correct
23 Correct 81 ms 47844 KB Output is correct
24 Correct 61 ms 48072 KB Output is correct
25 Correct 66 ms 48060 KB Output is correct
26 Correct 69 ms 47788 KB Output is correct
27 Correct 72 ms 48084 KB Output is correct
28 Correct 11 ms 18896 KB Output is correct
29 Correct 11 ms 18884 KB Output is correct
30 Correct 9 ms 18896 KB Output is correct
31 Correct 9 ms 18896 KB Output is correct
32 Correct 9 ms 18768 KB Output is correct
33 Correct 8 ms 18532 KB Output is correct
34 Correct 9 ms 18896 KB Output is correct
35 Correct 9 ms 18896 KB Output is correct
36 Correct 9 ms 18896 KB Output is correct
37 Correct 9 ms 18828 KB Output is correct
38 Correct 9 ms 18904 KB Output is correct
39 Correct 10 ms 18916 KB Output is correct
40 Correct 11 ms 18908 KB Output is correct
41 Correct 10 ms 18900 KB Output is correct
42 Correct 9 ms 18892 KB Output is correct
43 Correct 9 ms 18868 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18384 KB Output is correct
2 Correct 9 ms 18896 KB Output is correct
3 Correct 8 ms 18896 KB Output is correct
4 Correct 8 ms 18896 KB Output is correct
5 Correct 9 ms 18896 KB Output is correct
6 Correct 11 ms 18884 KB Output is correct
7 Correct 10 ms 18896 KB Output is correct
8 Correct 8 ms 18896 KB Output is correct
9 Incorrect 8 ms 18896 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 70136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -