Submission #1225035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225035		Sharky	Radio Towers (IOI22_towers)	C++20	0 / 100	127 ms	14068 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

int n, mx = 0, pos = 0;
vector<int> h;

const int N = 1e5 + 5;

int sp[19][N], lg2[N];
vector<pair<int, int>> srt;
vector<int> thres;
set<int> idx;

int query(int x, int y) {
    int j = lg2[y - x + 1];
    return max(sp[j][x], sp[j][y - (1 << j) + 1]);
}

void init(int _n, std::vector<int> H) {
    n = _n;
    h = H;
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
    for (int i = 0; i < n; i++) sp[0][i] = h[i], srt.push_back({h[i], i});
    sort(srt.begin(), srt.end());
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
    for (int i = 1; i < 19; i++) {
        for (int j = 0; j + (1 << i) - 1 < n; j++) {
            sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
    int D = 1, ans = 0;
    for (int i = 0; i < srt.size(); i++) {
        int x = srt[i].second;
        bool gone_wrong = 0;
        if (!idx.empty() && *idx.begin() < x) {
            int k = *--idx.lower_bound(x);
            if (query(k, x - 1) < h[x] + D) gone_wrong = 1;
        }
        if (!gone_wrong && !idx.empty() && *idx.rbegin() > x) {
            int k = *idx.lower_bound(x);
            if (query(x + 1, k) < h[x] + D) gone_wrong = 1;
        }
        if (!gone_wrong) {
            ans++;
            idx.insert(x);
        }
    }
    const int inf = 1e9;
    vector<int> pos;
    set<pair<int, pair<int, int>>> st;
    vector<int> l(n, -1), r(n, -1), lz(n, 0);
    for (auto& i : idx) pos.push_back(i);
    for (int i = 1; i < pos.size(); i++) {
        l[pos[i]] = pos[i - 1];
        st.insert({query(pos[i-1]+1, pos[i]-1) - max(h[pos[i-1]], h[pos[i]]), {pos[i-1], pos[i]}});
    }
    for (int i = 0; i + 1 < pos.size(); i++) r[pos[i]] = pos[i + 1];
    auto del = [&] (int x) {
        // cout << "delte " << x << '\n';
        int L = l[x], R = r[x];
        l[R] = L, r[L] = R;
    };
    while (!st.empty()) {
        auto [delta, pr] = *st.begin();
        // cout << "hi " << delta << " " << pr.first << " " << pr.second << '\n';
        st.erase({delta, pr});
        auto [ll, rr] = pr;
        if (lz[ll] || lz[rr]) continue;
        thres.push_back(delta);
        // cout << "pb " << delta << '\n';
        if (h[ll] > h[rr]) {
            lz[ll] = 1;
            int L = l[ll];
            del(ll);
            if (L != -1) st.insert({query(L+1, rr-1) - max(h[L], h[rr]), {L, rr}});
        } else {
            lz[rr] = 1;
            int R = r[rr];
            del(rr);
            if (R != -1) st.insert({query(ll+1, R-1) - max(h[ll], h[R]), {ll, R}});
        }
    }
    // for (auto& x : thres) cout << x << " ";
    // cout << '\n';
    sort(thres.begin(), thres.end());
    thres.push_back(inf+1);
}

int max_towers(int L, int R, int D) {
    D--;
    if (thres[0] > D) return thres.size();
    int x = thres.size() - (upper_bound(thres.begin(), thres.end(), D) - thres.begin());
    return x;
}

• 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