Submission #771769

#TimeUsernameProblemLanguageResultExecution timeMemory
771769drdilyorRadio Towers (IOI22_towers)C++17
17 / 100
1972 ms32320 KiB
#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; 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 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; } 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); return cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...