Submission #667085

#	Time	Username	Problem	Language	Result	Execution time	Memory
667085		tatyam	Radio Towers (IOI22_towers)	C++17	23 / 100	4019 ms	12048 KiB

towers

#include <bits/stdc++.h>
using namespace std;
template<class T> void chmax(T& a, T b){ if(a < b) a = b; }


int N;
vector<int> H;
vector<pair<int, int>> seg;
void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;
    seg.resize(N * 2);
    for(int i = 0; i < N; i++) seg[N + i] = {H[i], i};
    for(int i = N; --i; ){
        seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
    }
}
int argmax(int L, int R){
    L += N;
    R += N;
    pair<int, int> ans;
    while(L < R){
        if(L & 1) chmax(ans, seg[L++]);
        if(R & 1) chmax(ans, seg[--R]);
        L >>= 1; R >>= 1;
    }
    return ans.second;
}

int max_towers(int L, int R, int D) {
    auto dfs = [&](int L, int R, auto dfs) -> pair<int, int> {
        if(R - L == 0) return {0, INT_MAX};
        const int mid = argmax(L, R);
        const int x = H[mid];
        auto [c1, mn1] = dfs(L, mid, dfs);
        auto [c2, mn2] = dfs(mid + 1, R, dfs);
        if(c1 <= 1 && c2 <= 1){
            if(x - max(mn1, mn2) >= D) return {2, 0};
            return {1, min({mn1, mn2, x})};
        }
        if(c1 < c2){
            swap(c1, c2);
            swap(mn1, mn2);
        }
        if(c2 <= 1) return {c1 + (x - mn2 >= D), 0};
        return {c1 + c2, 0};
    };
    return dfs(L, R + 1, dfs).first;
}

• 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