제출 #763539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763539		drdilyor	Radio Towers (IOI22_towers)	C++17	23 / 100	4027 ms	15580 KiB

towers

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

template<typename T, typename Op>
struct SparseTable {
    vector<vector<T>> sparse;
    Op accum_func;

    SparseTable() = default;

    SparseTable(const vector<T>& arr, const Op func) : accum_func(func) {
        int n = arr.size();
        int logn = 32 - __builtin_clz(n);
        sparse.resize(logn, vector<T>(n));
        sparse[0] = arr;
        for (int lg = 1; lg < logn; lg++) {
            for (int i = 0; i + (1 << lg) <= n; i++) {
                sparse[lg][i] = accum_func(sparse[lg - 1][i], sparse[lg - 1][i + (1 << (lg - 1))]);
            }
        }
    }

    T find(int l, int r) { // [l, r]
        r++;
        int cur_log = 31 - __builtin_clz(r - l);
        return accum_func(sparse[cur_log][l], sparse[cur_log][r - (1 << cur_log)]);
    }
};

int st_min(int a, int b) { return min(a, b); }
int st_max(int a, int b) { return max(a, b); }

int n;
vector<int> h, ix;
SparseTable<int, decltype(&st_min)> hmax;
SparseTable<int, decltype(&st_max)> hmin;
void init(int N, std::vector<int> H) {
    n = N, h = H;
    ix.resize(n);
    iota(ix.begin(), ix.end(), 0);
    sort(ix.begin(), ix.end(), [&](int i, int j) {
            return h[i] < h[j];
            });
    hmax = SparseTable(h, st_max);
    hmin = SparseTable(h, st_min);
}

int max_towers(int L, int R, int D) {
    int res = 0;
    for (int i_ = 0; i_ < n; i_++) {
        int i = ix[i_];
        if (i < L || i > R) continue;
        bool ok = 1;
        {
            int l = L-1, r = i;
            while (l < r-1) {
                int mid = (l+r) / 2;
                if (hmax.find(mid, i) - h[i] >= D)
                    l = mid;
                else r = mid;
            }
            if (hmin.find(l+1, i) < h[i]) ok = 0;
        }
        {
            int l = i, r = R+1;
            while (l < r-1) {
                int mid = (l+r) / 2;
                if (hmax.find(i, mid) - h[i] >= D)
                    r = mid;
                else l = mid;
            }
            if (hmin.find(i, r-1) < h[i]) ok = 0;
        }
        res += ok;
    }
    return res;
}

• 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