Submission #712956

#	Time	Username	Problem	Language	Result	Execution time	Memory
712956		t6twotwo	Radio Towers (IOI22_towers)	C++17	23 / 100	4080 ms	13976 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<int> H, lg;
vector<vector<int>> st;
int query(int l, int r) {
    int k = __lg(r - l);
    return max(st[l][k], st[r - (1 << k)][k]);
}
void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    int lg = __lg(N);
    st.assign(N, vector<int>(lg + 1));
    for (int i = 0; i < N; i++) {
        st[i][0] = H[i];
    }
    for (int j = 0; j < lg; j++) {
        for (int i = 0; i + (2 << j) <= N; i++) {
            st[i][j + 1] = max(st[i][j], st[i + (1 << j)][j]);
        }
    }
}
int max_towers(int L, int R, int D) {
    R++;
    vector<int> p(R - L);
    iota(p.begin(), p.end(), L);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return H[i] < H[j];
    });
    set<int> s;
    int ans = 0;
    for (int i : p) {
        auto it = s.lower_bound(i);
        if (it != s.begin()) {
            int j = *prev(it);
            if (max(H[i], H[j]) > query(j, i + 1) - D) continue;
        }
        if (it != s.end()) {
            int j = *it;
            if (max(H[i], H[j]) > query(i, j + 1) - D) continue;
        }
        ans++;
        s.insert(i);
    }
    return ans;
}

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