#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/hp/contests/debug.h"
#else
#define debug(...) void(37)
#endif
constexpr int max_D = int(1e9) + 1;
template<typename T, typename F = function<T(const T&, const T&)>>
struct SparseTable {
vector<vector<T>> table;
int n;
F op;
SparseTable () {}
SparseTable(vector<T> a, F _op) : op(_op) {
n = int(a.size());
int lg = __lg(n) + 1;
table.resize(lg + 1);
table[0] = a;
for (int l = 1; l < lg; ++l) {
int s = n - (1 << l) + 1;
table[l].resize(s);
for (int i = 0; i < s; ++i) {
table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << (l - 1))]);
}
}
}
T get(int l, int r) {
int lg = __lg(r - l + 1);
return op(table[lg][l], table[lg][r - (1 << lg) + 1]);
}
};
constexpr int MAX_NODES = int(2e5) * 20 * 8;
int max_N = int(1e5);
namespace PST {
int t = 0;
struct info {
int first_r_id, last_l_id;
int ct;
info() { }
void init() {
first_r_id = -1, last_l_id = -1;
ct = 0;
}
};
info I() {
static info res;
res.init();
return res;
}
info unite(info l, info r) {
info res;
res.first_r_id = (l.first_r_id == -1 ? r.first_r_id : l.first_r_id);
res.last_l_id = (r.last_l_id == -1 ? l.last_l_id : r.last_l_id);
res.ct = l.ct + r.ct;
return res;
}
struct node {
int L, R;
info i;
void init() {
L = R = -1;
i.init();
}
void dupe(const node& x) {
L = x.L, R = x.R;
i = x.i;
}
};
node tree[MAX_NODES];
int new_node() {
tree[t].init();
t++;
return t - 1;
}
void pull(int v) {
tree[v].i = unite(tree[v].L == -1 ? I() : tree[tree[v].L].i, tree[v].R == -1 ? I() : tree[tree[v].R].i);
}
int modify(int v, int l, int r, int p, int x, int type) {
int new_v = new_node();
if (v != -1) {
tree[new_v].dupe(tree[v]);
} else {
tree[new_v].init();
}
v = new_v;
if (l == r) {
if (type) {
tree[v].i.first_r_id = x;
} else {
tree[v].i.last_l_id = x;
tree[v].i.ct = (x != -1);
}
//debug("update", v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);
return v;
}
int mid = (l + r) >> 1;
if (p <= mid) {
tree[v].L = modify(tree[v].L, l, mid, p, x, type);
} else {
tree[v].R = modify(tree[v].R, mid + 1, r, p, x, type);
}
pull(v);
//debug("pull", v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);
return v;
}
info get(int v, int l, int r, int ll, int rr) {
//debug(v, l, r, tree[v].i.ct, tree[v].i.first_r_id, tree[v].i.last_l_id);
if (l >= ll && rr >= r) {
return tree[v].i;
}
int mid = (l + r) >> 1;
info res;
res.init();
if (ll <= mid && tree[v].L != -1) {
res = unite(res, get(tree[v].L, l, mid, ll, rr));
}
if (mid < rr && tree[v].R != -1) {
res = unite(res, get(tree[v].R, mid + 1, r, ll, rr));
}
return res;
}
int modify_L(int tree_id, int p, int v) {
return modify(tree_id, 0, max_N, p, v, 0);
}
int modify_R(int tree_id, int p, int v) {
return modify(tree_id, 0, max_N, p, v, 1);
}
array<int, 3> get_ids(int tree_id, int l, int r) {
auto i = get(tree_id, 0, max_N, l, r);
return {i.first_r_id, i.last_l_id, i.ct};
}
};
int N, LG, root;
vector<int> H, L, R;
vector<vector<int>> lift;
SparseTable<int> min_H, max_H;
int S;
vector<int> times, segtrees;
int get_time(int x) {
assert(times[0] <= x);
return int(lower_bound(times.begin(), times.end(), x + 1) - times.begin()) - 1;
}
void init(int _N, std::vector<int> _H) {
N = _N; H = _H;
LG = __lg(N) + 1;
vector<int> foo(N); iota(foo.begin(), foo.end(), 0);
min_H = SparseTable<int>(foo, [&](int x, int y) {
return (H[x] < H[y] ? x : y);
});
max_H = SparseTable<int>(foo, [&](int x, int y) {
return (H[x] > H[y] ? x : y);
});
vector<vector<int>> g(N);
L.resize(N), R.resize(N);
lift.resize(LG, vector<int>(N, -1));
auto mn = H;
auto Dfs = [&](int l, int r, auto&& Dfs) -> int {
int v = max_H.get(l, r);
L[v] = l, R[v] = r;
if (l != v) {
g[v].push_back(Dfs(l, v - 1, Dfs));
}
if (r != v) {
g[v].push_back(Dfs(v + 1, r, Dfs));
}
for (auto u : g[v]) {
mn[v] = min(mn[v], mn[u]);
lift[0][u] = v;
}
return v;
};
root = Dfs(0, N - 1, Dfs);
debug(root, L, R, lift);
for (int l = 1; l < LG; ++l) {
for (int i = 0; i < N; ++i) {
int next = lift[l - 1][i];
if (next == -1) {
lift[l][i] = -1;
} else {
lift[l][i] = lift[l - 1][next];
}
}
}
vector<int> act_t(N), dis_t(N);
for (int i = 0; i < N; ++i) {
act_t[i] = H[i] - mn[i] + 1;
}
for (int i = 0; i < N; ++i) {
int p = lift[0][i];
dis_t[i] = (p == -1 ? max_D : H[p] - mn[i] + 1);
}
debug(act_t, dis_t);
// each segment is active in the range [act_t_i, dis_t_i)
for (int i = 0; i < N; ++i) {
times.push_back(act_t[i]);
times.push_back(dis_t[i]);
}
sort(times.begin(), times.end());
times.erase(unique(times.begin(), times.end()), times.end());
S = int(times.size());
vector<vector<int>> updates(S);
for (int i = 0; i < N; ++i) {
updates[get_time(dis_t[i])].push_back(~i);
updates[get_time(act_t[i])].push_back(i);
}
int segtree = PST::new_node();
for (int i = 0; i < S; ++i) {
for (auto x : updates[i]) {
int val, ind;
if (x < 0) {
ind = ~x;
val = -1;
} else {
ind = x;
val = x;
}
debug(ind, val, L[ind], R[ind]);
segtree = PST::modify_L(segtree, L[ind], val);
segtree = PST::modify_R(segtree, R[ind], val);
}
//debug(i, segtree);
segtrees.push_back(segtree);
}
}
int max_towers(int QL, int QR, int D) {
int t = get_time(D);
debug(QL, QR, D, t);
int st_id = segtrees[t];
int first_r = PST::get_ids(st_id, 0, QL)[1];
int last_l = PST::get_ids(st_id, QR, max_N)[0];
//auto[first_r, last_l, foo] = PST::get_ids(st_id, QL, QR);
debug(first_r, last_l, st_id);
int ll = (first_r == -1 ? 0 : R[first_r] + 1);
int rr = (last_l == -1 ? max_N : L[last_l] - 1);
auto[l_block, r_block, inside] = (ll <= rr ? PST::get_ids(st_id, ll, rr) : array<int, 3>{-1, -1, 0});
auto Binary_lift = [&](int v, function<bool(int)> good) {
for (int l = LG - 1; l >= 0; --l) {
int u = lift[l][v];
if (u != -1 && !good(u)) {
v = u;
}
}
return v;
};
if (first_r != -1) {
first_r = Binary_lift(first_r, [&](int x) {
return H[x] - min_H.get(QL, R[x]) >= D;
});
}
if (last_l != -1) {
last_l = Binary_lift(last_l, [&](int x) {
return H[x] - min_H.get(L[x], QR) >= D;
});
}
if (l_block == -1) {
if (first_r != -1 && last_l != -1 && R[first_r] < L[last_l]) {
return 2;
}
return 1;
}
if (first_r != -1 && R[first_r] < L[l_block]) ++inside;
if (last_l != -1 && L[last_l] > R[r_block]) ++inside;
return inside;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
119 ms |
192920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
308040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
42956 KB |
15032nd lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
119 ms |
192920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
