Submission #771786

#	Time	Username	Problem	Language	Result	Execution time	Memory
771786		drdilyor	Radio Towers (IOI22_towers)	C++17	17 / 100	1739 ms	32284 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
using ll = long long;
constexpr int inf = 1e9;

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)]);
    }
};

struct SegmentTree {
    using T = vector<int>;
    using S = int;
    const T id = {};
    inline T single(S v) { return {v}; }

    T merge(const T& l, const T& r) {
        T res(l.size() + r.size());
        std::merge(l.cbegin(), l.cend(),
              r.cbegin(), r.cend(),
              res.begin());
        return res;
    }

    int n;
    vector<T> tree;

    SegmentTree() = default;
    void init(vector<S> arr) {
        n = arr.size();
        tree.resize(n * 2, id);
        for (int i = 0; i < n; i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, S v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    tuple<int,int,int> query(int l, int r, int x) {
        int cnt = 0;
        int left = -1, right = -1;
        l += n; r += n;
        while (l <= r) {
            if (l % 2 == 1) {
                if (left ==-1) left = leftmost(l, x);
                cnt += count_ge(tree[l++], x);
            }
            if (r % 2 == 0) {
                if (right == -1) right = rightmost(r, x);
                cnt += count_ge(tree[r--], x);
            }
            l /= 2; r /= 2;
        }
        return {cnt, left, right};
    }

    int count_ge(T& v, int x) {
        return v.end() - lower_bound(v.begin(), v.end(), x);
    }

    int leftmost(int v, int x, bool rev=0) {
        if (tree[v].back() < x) return -1;
        while (v < n) {
            if (tree[v*2+rev].back() >= x) v = v * 2 +rev;
            else v = v * 2 + 1 -rev;
        }
        return v - n;
    }
    int rightmost(int v, int x) {
        return leftmost(v, x, 1);
    }
};


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;

vector<int> start;
SegmentTree ans;

int find_left(int i, int d) {
    int 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;
    }
    return l;
}

int find_right(int i, int d) {
    int l = i, r = n;
    while (l < r-1) {
        int mid = (l+r) / 2;
        if (hmax.find(i, mid) - h[i] >= d)
            r = mid;
        else l = mid;
    }
    return r;
}

void init(int N, std::vector<int> H) {
    n = N, h = H;
    ix.resize(n);
    start.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);
    const int L = 0, R = n-1;

    for (int i = 0; i < n;i++) {
        int lD = 0, rD = inf+1;
        while (lD < rD-1) {
            int D = (lD + rD) / 2;
            bool ok = 1;

            int lg = find_left(i, D);
            if (hmin.find(lg+1, i) < h[i]) ok = 0;

            int rg = find_right(i, D);
            if (hmin.find(i, rg-1) < h[i]) ok = 0;

            if (ok) lD = D;
            else rD = D;
        }
        start[i] = lD;
    }
    ans.init(start);
}

int max_towers(int L, int R, int D) {
    auto [cnt, left, right] = ans.query(L, R, D);
    int lg = find_left(left, D);
    int rg = find_right(right, D);
    if (lg > L && hmin.find(L, lg) <= h[lg]-D) cnt++;
    if (rg < R && hmin.find(rg, R) <= h[rg]-D) cnt++;
    return cnt;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:151:15: warning: unused variable 'L' [-Wunused-variable]
  151 |     const int L = 0, R = n-1;
      |               ^
towers.cpp:151:22: warning: unused variable 'R' [-Wunused-variable]
  151 |     const int L = 0, R = n-1;
      |                      ^

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