Submission #819885

#	Time	Username	Problem	Language	Result	Execution time	Memory
819885		finn__	Radio Towers (IOI22_towers)	C++17	100 / 100	1134 ms	48092 KiB

towers

#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, x, 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;
    }
}

size_t left_intermediate(size_t i, int64_t d)
{
    if (!i || hmax.range_max(0, i - 1) < h[i] + d)
        return SIZE_MAX;
    size_t a = 0, b = i - 1;
    while (a < b)
    {
        size_t const mid = (a + b + 1) >> 1;
        if (hmax.range_max(mid, i - 1) >= h[i] + d)
            a = mid;
        else
            b = mid - 1;
    }
    return a;
}

size_t right_intermediate(size_t i, int64_t d)
{
    if (i == n - 1 || hmax.range_max(i + 1, n - 1) < h[i] + d)
        return SIZE_MAX;
    size_t a = i + 1, b = n - 1;
    while (a < b)
    {
        size_t const mid = (a + b) >> 1;
        if (hmax.range_max(i + 1, mid) >= h[i] + d)
            b = mid;
        else
            a = mid + 1;
    }
    return a;
}

bool match_left(size_t i, size_t l, int64_t d)
{
    size_t j = left_intermediate(i, d);
    if (j == SIZE_MAX || j <= l)
        return 0;
    return ltree.max_diff(l, j) >= d;
}

bool match_right(size_t i, size_t r, int64_t d)
{
    size_t j = right_intermediate(i, d);
    if (j == SIZE_MAX || j >= r)
        return 0;
    return rtree.max_diff(j, r) >= d;
}

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 + (match_left(smallest, l, d) || match_right(smallest, r, d));
    }
    else
    {
        size_t u = leftmost_nonzero(l, r, rt),
               v = rightmost_nonzero(l, r, rt);
        return y + match_left(u, l, d) + match_right(v, r, d);
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23