#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "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_id, last_id;
int ct;
info() { }
void init() {
first_id = -1, last_id = -1;
ct = 0;
}
};
info I() {
static info res;
res.init();
return res;
}
info unite(info l, info r) {
info res;
res.first_id = (l.first_id == -1 ? r.first_id : l.first_id);
res.last_id = (r.last_id == -1 ? l.last_id : r.last_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 new_v = new_node();
if (v != -1) {
tree[new_v].dupe(tree[v]);
} else {
tree[new_v].init();
}
v = new_v;
if (l == r) {
tree[v].i.last_id = tree[v].i.first_id = x;
tree[v].i.ct = (x != -1);
return v;
}
int mid = (l + r) >> 1;
if (p <= mid) {
tree[v].L = modify(tree[v].L, l, mid, p, x);
} else {
tree[v].R = modify(tree[v].R, mid + 1, r, p, x);
}
pull(v);
//debug("pull", v, l, r, tree[v].i.ct, tree[v].i.first_id, tree[v].i.last_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_id, tree[v].i.last_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(int tree_id, int p, int v) {
return modify(tree_id, 0, max_N, p, v);
}
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_id, i.last_id, i.ct};
}
};
int N, LG, root;
vector<int> H, L, R, tour, tin, tout;
SparseTable<int> min_H, max_H, lca_st;
int get_lca(int v, int u) {
debug(v, u, tin[v], tout[v], tin[u], tout[u]);
if (tin[v] > tin[u]) {
swap(v, u);
}
if (tout[v] >= tout[u]) {
return v;
}
return lca_st.get(tout[v], tin[u]);
}
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) {
debug("hello?");
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), tin.resize(N), tout.resize(N);
vector<int> par(N, -1);
vector<int> mn(N); iota(mn.begin(), mn.end(), 0);
auto Dfs = [&](int l, int r, auto&& Dfs) -> int {
int v = max_H.get(l, r);
tin[v] = int(tour.size());
tour.push_back(v);
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]) {
if (H[mn[u]] < H[mn[v]]) mn[v] = mn[u];
mn[v] = min(mn[v], mn[u]);
par[u] = v;
tour.push_back(v);
}
tout[v] = int(tour.size()) - 1;
return v;
};
root = Dfs(0, N - 1, Dfs);
debug(L, R);
lca_st = SparseTable<int>(tour, [&](int x, int y) {
return H[x] > H[y] ? x : y;
});
vector<int> act_t(N), dis_t(N);
for (int i = 0; i < N; ++i) {
act_t[i] = H[i] - H[mn[i]] + 1;
}
for (int i = 0; i < N; ++i) {
int p = par[i];
dis_t[i] = (p == -1 ? max_D : H[p] - H[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 = mn[~x];
val = -1;
} else {
ind = mn[x];
val = mn[x];
}
debug(ind, val, L[ind], R[ind]);
segtree = PST::modify(segtree, ind, val);
}
//debug(i, segtree);
segtrees.push_back(segtree);
}
}
int max_towers(int QL, int QR, int D) {
int t = get_time(D);
auto[l, r, ct] = PST::get_ids(segtrees[t], QL, QR);
int prev_id = (QL > 0 ? PST::get_ids(segtrees[t], 0, QL - 1)[1] : -1);
int next_id = (QR < N - 1 ? PST::get_ids(segtrees[t], QR + 1, N - 1)[0] : -1);
debug(l, r, prev_id, next_id);
if (l == -1) {
if (prev_id == -1 || next_id == -1) {
return 1;
}
int lca = get_lca(prev_id, next_id);
assert(l <= lca && r <= lca);
if (QL < lca && lca < QR && H[lca] - max(H[min_H.get(QL, lca)], H[min_H.get(lca, QR)]) >= D) {
return 2;
} else {
return 1;
}
} else {
if (prev_id != -1) {
int lca = get_lca(prev_id, l);
debug(lca);
if (QL < lca && H[lca] - max(H[l], H[min_H.get(QL, lca)]) >= D) {
ct++;
}
}
if (next_id != -1) {
int lca = get_lca(r, next_id);
if (lca < QR && H[lca] - max(H[min_H.get(lca, QR)], H[r]) >= D) {
ct++;
}
}
return ct;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
330 ms |
73356 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3160 KB |
1st lines differ - on the 1st token, expected: '292', found: '242' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3160 KB |
1st lines differ - on the 1st token, expected: '292', found: '242' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
584 ms |
112576 KB |
1st lines differ - on the 1st token, expected: '11903', found: '11902' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
26260 KB |
1st lines differ - on the 1st token, expected: '7197', found: '6464' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3160 KB |
1st lines differ - on the 1st token, expected: '292', found: '242' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
330 ms |
73356 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
