Submission #763555

#TimeUsernameProblemLanguageResultExecution timeMemory
763555drdilyorRadio Towers (IOI22_towers)C++17
17 / 100
1981 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]); } int query(int l, int r, int x) { int cnt = 0; l += n; r += n; while (l <= r) { if (l % 2 == 1) cnt += count_ge(tree[l++], x); if (r % 2 == 0) cnt += count_ge(tree[r--], x); l /= 2; r /= 2; } return cnt; } int count_ge(T& v, int x) { return v.end() - lower_bound(v.begin(), v.end(), x); } }; 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) { return ans.query(0, n-1, D); }
#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...