Submission #803002

#	Time	Username	Problem	Language	Result	Execution time	Memory
803002		adrilen	Radio Towers (IOI22_towers)	C++17	17 / 100	876 ms	5288 KiB

towers

#include "towers.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
constexpr int maxn = 1e5 + 5;
int n;

int h[maxn], ledge[maxn] = { 0 }, redge[maxn] = { 0 }, owner[maxn] = { 0 };
bool removed[maxn] = { 0 };

int out = 0;
void uni(int a, int b)
{
    assert(a != b);
    
    out--;
    h[a] = min(h[a], h[b]);
    ledge[a] = min(ledge[a], ledge[b]);
    redge[a] = max(redge[a], redge[b]);
    owner[ledge[a] + 1] = owner[redge[a] - 1] = a;
    removed[b] = true;
}


vector <arr> output; // {d val, output}

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

    for (int i = 0; i < n; i++) h[i + 1] = H[i];
    h[0] = h[n + 1] = 2e9;

    vector <arrr> edges;        // {height diff, from, to}
    edges.reserve(n - 1);

    vector <int> minima;

    for (int i = 1; i <= n; i++) {
        if (h[i - 1] > h[i] && h[i] < h[i + 1]) {
            minima.emplace_back(i);
        }
    }


    priority_queue <arr, vector<arr>, greater<arr>> pq;

    for (int i : minima)
    {
        ledge[i] = i - 1, redge[i] = i + 1;
        owner[i] = i;
        if (i != 1) pq.push(arr{h[ledge[i]] - h[i], i});
        if (i != n) pq.push(arr{h[redge[i]] - h[i], i});
    }

    out = minima.size();

    int d = 1;
    arr a;
    while (!pq.empty())
    {
        a = pq.top();
        pq.pop();

        if (removed[a[1]]) continue;

        if (a[0] >= d) {        // Might not get last
            
            output.emplace_back(arr{d, out});
            d = a[0] + 1;
        }

        // Left side
        if (h[ledge[a[1]]] - h[a[1]] == a[0])
        {
            int i = ledge[a[1]] - 1;
            while (i > 0 && owner[i] == 0 && h[i] <= h[ledge[a[1]]]) i--;

            if (owner[i] != 0) {
                uni(owner[i], a[1]);
                if (ledge[owner[i]] != 0) pq.emplace(arr{h[ledge[owner[i]]] - h[owner[i]], owner[i]});
                if (redge[owner[i]] != n + 1) pq.emplace(arr{h[redge[owner[i]]] - h[owner[i]], owner[i]});
            } else if (h[i] > h[ledge[a[1]]])
            {
                ledge[a[1]] = i;
                owner[i + 1] = a[1];
                if (i != 0) pq.emplace(arr{h[i] - h[a[1]], a[1]});
            }
        }

        // Right side
        if (h[redge[a[1]]] - h[a[1]] == a[0])
        {
            int i = redge[a[1]] + 1;
            while (i <= n && owner[i] == 0 && h[i] <= h[redge[a[1]]]) i++;

            if (owner[i] != 0)
            {
                uni(a[1], owner[i]);
                if (redge[a[1]] != n + 1) pq.emplace(arr{h[redge[a[1]]] - h[a[1]], a[1]});
                if (ledge[a[1]] != 0) pq.emplace(arr{h[ledge[a[1]]] - h[a[1]], a[1]});
            } else if (h[i] > h[redge[a[1]]])
            {
                redge[a[1]] = i;
                owner[i - 1] = a[1];
                if (i != n + 1) pq.emplace(arr{h[i] - h[a[1]], a[1]});
            }
        }
        // cout << "a: " << a[0] << " " << a[1] << " " << ledge[a[1]] << " " << redge[a[1]] << "\n";
    }   
    if (d != output.back()[0])
    {
        output.emplace_back(arr{d, out});
    }

    // for (auto &i : output) {
    //     cout << i[0] << " " << i[1] <<"\n";
    // }
}

int max_towers(int l, int r, int d) {
    if (r - l < 2) return 1;

    auto it = lower_bound(output.begin(), output.end(), arr{d, (int)2e9}) - 1;


    return (*it)[1];
}

• 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