#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();
while (n & (n-1)) n++;
tree.resize(n * 2, id);
for (int i = 0; i < (int)arr.size(); 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 leftmost(int v, int x) {
if (tree[v].back() < x) return -1;
while (v < n) {
if (tree[v*2].back() >= x) v = v * 2;
else v = v * 2 + 1;
}
return v - n;
}
int rightmost(int v, int x) {
if (tree[v].back() < x) return -1;
while (v < n) {
if (tree[v*2+1].size() && tree[v*2+1].back() >= x) v = v * 2 + 1;
else v = v * 2;
}
return v - n;
}
int find_leftmost(int l, int r, int x, int v, int tl, int tr) {
if (l <= tl && tr <= r) return leftmost(v, x);
if (tr < l || r < tl) return -1;
int mid = (tl+tr) / 2;
int ans = find_leftmost(l, r, x, v * 2, tl, mid);
if (ans != -1) return ans;
return find_leftmost(l, r, x, v * 2 + 1, mid+1, tr);
}
int find_rightmost(int l, int r, int x, int v, int tl, int tr) {
if (l <= tl && tr <= r) return rightmost(v, x);
if (tr < l || r < tl) return -1;
int mid = (tl+tr) / 2;
int ans = find_rightmost(l, r, x, v * 2 + 1, mid+1, tr);
if (ans != -1) return ans;
return find_rightmost(l, r, x, v * 2, tl, mid);
}
int find_leftmost(int l, int r, int x) {
return find_leftmost(l, r, x, 1, 0, n-1);
}
int find_rightmost(int l, int r, int x) {
return find_rightmost(l, r, x, 1, 0, n-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);
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);
for (int i : H) cout << i << ' '; cout << endl;
for (int i : start) cout << i << ' '; cout << endl;
}
int max_towers(int L, int R, int D) {
int cnt = ans.query(L, R, D);
int left = ans.find_leftmost(L, R, D);
int right = ans.find_rightmost(L, R, D);
int lg = left == -1 ? -1 : find_left(left, D);
int rg = right == -1 ? n : find_right(right, D);
// cout << cnt << ' ' << left << ' ' << right << '\n'; cout << lg << ' ' << rg << endl;
if (lg > L && hmin.find(L, lg) <= h[lg]-D) cnt++;
if (rg < R && hmin.find(rg, R) <= h[rg]-D) cnt++;
return max(1, cnt);
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:199:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
199 | for (int i : H) cout << i << ' '; cout << endl;
| ^~~
towers.cpp:199:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
199 | for (int i : H) cout << i << ' '; cout << endl;
| ^~~~
towers.cpp:200:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
200 | for (int i : start) cout << i << ' '; cout << endl;
| ^~~
towers.cpp:200:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
200 | for (int i : start) cout << i << ' '; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
430 ms |
19068 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
804 ms |
33688 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
163 ms |
7744 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
430 ms |
19068 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
