Submission #800033

#	Time	Username	Problem	Language	Result	Execution time	Memory
800033		jakobrs	Radio Towers (IOI22_towers)	C++17	17 / 100	808 ms	6536 KiB

towers

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

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

std::map<int, int> data;

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

    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.insert_or_assign(2'000'000'000, towers);
}

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

    return data.lower_bound(D)->second;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:52: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]
   52 |     for (int i = 1; i < adj.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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