Submission #711594

#	Time	Username	Problem	Language	Result	Execution time	Memory
711594		t6twotwo	Radio Towers (IOI22_towers)	C++17	0 / 100	4059 ms	1720 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 f(int i, int j) {
    return H[i] > H[j] ? i : j;
}
int query(int l, int r) {
    int k = lg[r - l];
    return f(st[l][k], st[r - (1 << k)][k]);
}
void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    // lg.resize(N + 1);
    // for (int i = 2; i <= N; i++) {
    //     lg[i] = lg[i / 2] + 1;
    // }
    // st.assign(N, vector<int>(lg[N] + 1));
    // for (int i = 0; i < N; i++) {
    //     fill(st[i].begin(), st[i].end(), i);
    // }
    // for (int j = 0; j < lg[N]; j++) {
    //     for (int i = 0; i + (2 << j) <= N; j++) {
    //         st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
    //     }
    // }
}
int max_towers(int L, int R, int D) { R++;
    auto dc = [&](auto dc, int l, int r, int lim) -> int {
        if (l >= r) return 0;
        int x = l, mn = H[l];
        for (int i = l; i < r; i++) {
            if (H[i] > H[x]) x = i;
            mn = min(mn, H[i]);
        }
        return max(mn + D <= lim ? 1 : 0, (l + 1 == x ? 1 : dc(dc, l, x - 1, H[x] - D)) + (r - 2 == x ? 1 : dc(dc, x + 1, r, H[x] - D)));
    };
    return dc(dc, L, R, 1 << 30);
}

• 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