oj.uz

Submission #799988

# Submission time Handle Problem Language Result Execution time Memory
799988 2023-08-01T09:09:43 Z jakobrs Radio Towers (IOI22_towers) C++17
0 / 100
 796 ms 6140 KB 
#include <algorithm>
#include <map>
#include <memory>
#include <optional>
#include <queue>
#include <unordered_set>
#include <vector>

#ifndef EVAL
#include <format>
#include <iostream>

template <typename... Args>
void print(std::format_string<Args...> fmt, Args &&...args) {
    std::cerr << std::format(fmt, std::forward<Args>(args)...);
}

template <typename... Args>
void println(std::format_string<Args...> fmt, Args &&...args) {
    std::cerr << std::format(fmt, std::forward<Args>(args)...) << '\n';
}
#else
#define print(...) ((void)0)
#define println(...) ((void)0)
#endif

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;
        int pos;
    };
    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,
                       .pos = i});
    }

    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.insert_or_assign(priority, towers);

        if (H[adj[from].pos] > H[adj[to].pos]) {
            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[adj[to].prev].pos],
                                                    H[adj[to].pos]),
                         .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[adj[from].pos],
                                                    H[adj[adj[from].next].pos]),
                         .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

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

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 631 ms 6100 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 1608 KB Output is correct
2 Incorrect 796 ms 6140 KB 748th lines differ - on the 1st token, expected: '12451', found: '12450'
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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