Submission #819758

#	Time	Username	Problem	Language	Result	Execution time	Memory
819758		finn__	Radio Towers (IOI22_towers)	C++17	0 / 100	464 ms	14624 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()); }

    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();

        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()); }

    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();

        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;
    }
};

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

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

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

max_segtree<int64_t, L> hmax;

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);
}

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)
{
    {
        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]);

    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;

    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)
{
    return range_sum(l, r, get_root(d));
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:131:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |         for (size_t i = 0; i < n; ++i)
      |                            ~~^~~
towers.cpp:142:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |         for (size_t i = 0; i < n; ++i)
      |                            ~~^~~
towers.cpp:153:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  153 |         for (size_t i = n - 1; i < n; --i)
      |                                ~~^~~
towers.cpp:164:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  164 |         for (size_t i = n - 1; i < n; --i)
      |                                ~~^~~
towers.cpp:173:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  173 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
towers.cpp:177:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  177 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~

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