Submission #800059

#	Time	Username	Problem	Language	Result	Execution time	Memory
800059		jakobrs	Radio Towers (IOI22_towers)	C++17	77 / 100	985 ms	26364 KiB

towers

#include <algorithm>
#include <optional>
#include <unordered_set>
#include <vector>
#include <map>
#include <queue>

int n;
std::vector<int> h;

int max_idx;
std::map<int, int> data;

void init(int N, std::vector<int> H) {
    n = N;
    h = H;

    max_idx = 0;
    for (int i = 1; i < N; i++) {
        if (H[i] > H[max_idx]) {
            max_idx = i;
        }
    }

    int towers = 0;

    struct D {
        int prev;
        int max_to_prev;
        int next;
        int max_to_next;
    };
    std::vector<D> adj;

    for (int i = 0; i < N; i++) {
        towers += 1;
        int max_to_prev = H[i];
        int max_to_next = H[i];
        if (i != 0) max_to_prev = std::max(max_to_prev, H[i - 1]);
        if (i + 1 != N) max_to_next = std::max(max_to_next, H[i + 1]);
        adj.push_back({.prev = i - 1,
                       .max_to_prev = max_to_prev,
                       .next = i + 1 == N ? -1 : i + 1,
                       .max_to_next = max_to_next});
    }

    struct PQItem {
        int priority;
        int from;
        int to;

        bool operator<(const PQItem &rhs) const {
            return priority > rhs.priority;
        }
    };

    std::vector<bool> active(adj.size(), true);
    std::priority_queue<PQItem> pq;
    for (int i = 1; i < adj.size(); i++) {
        pq.push({.priority = 0, .from = i - 1, .to = i});
    }

    while (!pq.empty()) {
        auto [priority, from, to] = pq.top();
        pq.pop();

        if (!active[from] || !active[to]) continue;

        data.emplace(priority, towers);

        if (H[from] > H[to]) {
            int max = adj[to].max_to_prev =
                std::max(adj[from].max_to_prev, adj[to].max_to_prev);
            adj[to].prev = adj[from].prev;
            if (adj[to].prev != -1) {
                adj[adj[to].prev].next = to;
                pq.push({.priority = max - std::max(H[adj[to].prev], H[to]),
                         .from = adj[to].prev,
                         .to = to});
            }
            towers -= 1;
            active[from] = false;
        } else {
            int max = adj[from].max_to_next =
                std::max(adj[from].max_to_next, adj[to].max_to_next);
            adj[from].next = adj[to].next;
            if (adj[from].next != -1) {
                adj[adj[from].next].prev = from;
                pq.push({.priority = max - std::max(H[from], H[adj[from].next]),
                         .from = from,
                         .to = adj[from].next});
            }
            towers -= 1;
            active[to] = false;
        }
    }

    data.emplace(2'000'000'000, towers);
}

template <typename Node>
struct SegmentTree {
    std::vector<Node> nodes;
    int offset;

    explicit SegmentTree(int sz) : nodes(2 * sz), offset(sz) {}

    void update(int idx, const Node &node) {
        idx += offset;
        nodes[idx] = node;

        while (idx /= 2) {
            nodes[idx] = nodes[2 * idx] * nodes[2 * idx + 1];
        }
    }

    Node query(int l, int r) const {
        Node left, right;

        l += offset;
        r += offset;

        while (l < r) {
            if (l & 1) left = left * nodes[l++];
            if (r & 1) right = nodes[--r] * right;

            l >>= 1;
            r >>= 1;
        }

        return left * right;
    }
};

int d;

struct LeftNode {
    int a, b, min, max;

    LeftNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
    LeftNode(int a) : a(-1), b(-1), min(a), max(a) {}
    LeftNode(int a, int b, int min, int max) : a(a), b(b), min(min), max(max) {}

    LeftNode operator*(const LeftNode &rhs) const {
        std::pair<int, int> c1 = {b, a};
        std::pair<int, int> c2 = {rhs.b, rhs.a};
        std::pair<int, int> c3 = {-1, -1};
        if (rhs.max >= 0 && rhs.max - min >= d) {
            c3 = {rhs.max, min};
        }

        std::pair<int, int> best = std::max(std::max(c1, c2), c3);

        return {best.second, best.first, std::min(min, rhs.min),
                std::max(max, rhs.max)};
    }
};
struct RightNode {
    int a, b, min, max;

    RightNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
    RightNode(int a) : a(-1), b(-1), min(a), max(a) {}
    RightNode(int a, int b, int min, int max)
        : a(a), b(b), min(min), max(max) {}

    RightNode operator*(const RightNode &rhs) const {
        std::pair<int, int> c1 = {b, a};
        std::pair<int, int> c2 = {rhs.b, rhs.a};
        std::pair<int, int> c3 = {-1, -1};
        if (max >= 0 && max - rhs.min >= d) {
            c3 = {max, rhs.min};
        }

        std::pair<int, int> best = std::max(std::max(c1, c2), c3);

        return {best.second, best.first, std::min(min, rhs.min),
                std::max(max, rhs.max)};
    }
};

struct PrecomputedData {
    std::unordered_set<int> included_s;
    std::vector<int> prefix_sums, prev, next;

    SegmentTree<LeftNode> left_st;
    SegmentTree<RightNode> right_st;
};

std::optional<PrecomputedData> precomputed;

int max_towers(int L, int R, int D) {
    if (L == R) return 1;
    R += 1;

    if (!precomputed) {
        d = D;
        std::vector<int> included{h[0]};
        int intermediary = h[0];
        for (int i = 1; i < n; i++) {
            if (h[i] > intermediary) {
                intermediary = h[i];
            } else if (intermediary - included.back() < D) {
                if (h[i] < included.back()) {
                    included.pop_back();
                    included.push_back(h[i]);
                    intermediary = h[i];
                }
            } else if (intermediary - h[i] >= D) {
                included.push_back(h[i]);
                intermediary = h[i];
            }
        }

        std::unordered_set<int> included_s(included.begin(), included.end());

        std::vector<int> prev, next;
        int prev_val = -1;
        for (int i = 0; i < n; i++) {
            if (included_s.count(h[i])) {
                prev_val = i;
            }
            prev.push_back(prev_val);
        }
        int next_val = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (included_s.count(h[i])) {
                next_val = i;
            }
            next.push_back(next_val);
        }
        std::reverse(next.begin(), next.end());
        std::vector<int> prefix_sums{1};
        prefix_sums.reserve(n + 1);
        for (int i = 0; i < n; i++) {
            prefix_sums.push_back(prefix_sums.back() + included_s.count(h[i]));
        }

        int o = 1;
        while (o < n) o *= 2;

        SegmentTree<LeftNode> left_st(o);
        SegmentTree<RightNode> right_st(o);

        for (int i = 0; i < n; i++) {
            left_st.update(i, LeftNode(h[i]));
            right_st.update(i, RightNode(h[i]));
        }

        precomputed = std::make_optional(PrecomputedData{
            included_s, prefix_sums, prev, next, left_st, right_st});
    }

    if (L == 0 && R == n) {
        return data.lower_bound(D)->second;
    }

    if (D != d) {
        if (R - 1 <= max_idx) {
            return 1;
        }
        if (L >= max_idx) {
            return 1;
        }

        int a = h[L];
        int b = h[R - 1];
        int c = h[max_idx];

        if (c - a >= D && c - b >= D) {
            return 2;
        } else {
            return 1;
        }
    }

    int total = precomputed->prefix_sums[R] - precomputed->prefix_sums[L];

    int next = precomputed->next[L];
    auto q0 = precomputed->left_st.query(L, next);
    if (q0.b - h[next] >= D) {
        total += 1;
    }

    int prev = precomputed->prev[R - 1];
    auto q1 = precomputed->right_st.query(prev + 1, R);
    if (q1.b - h[prev] >= D) {
        total += 1;
    }

    return std::max(total, 1);
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<init(int, std::vector<int>)::D>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 1; i < adj.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• 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: 0 / 23