#include <bits/stdc++.h>
constexpr const int MXH = (int) 1e9 + 5;
struct Sparse {
struct Item {
int mn = MXH, mx = -MXH, anl = 0, anr = 0;
static Item merge(const Item& l, const Item& r) {
return {
std::min(l.mn, r.mn), std::max(l.mx, r.mx),
std::max({ l.anl, r.anl, r.mx - l.mn }), std::max({ l.anr, r.anr, l.mx - r.mx })
};
}
};
int size;
std::vector <std::vector <Item>> bin;
void init(const std::vector <int>& v) {
bin.resize(17, std::vector <Item> (size = v.size()));
for (int i = 0; i < size; i++) bin[0][i].mn = bin[0][i].mx = v[i];
for (int b = 1; b < 17; b++)
for (int i = 0; i + (1 << (b - 1)) < size; i++)
bin[b][i] = Item::merge(bin[b - 1][i], bin[b - 1][i + (1 << (b - 1))]);
}
Item query(int l, int r) {
Item res;
if (l >= r || l < 0 || r >= size) return res;
for (int b = 31 - __builtin_clz(r - l), range = r - l; ~b; l += 1 << b--)
if (range & (1 << b))
res = Item::merge(res, bin[b][l]);
return res;
}
};
struct PNode {
struct Item {
int sum = 0;
int mn = MXH, mx = -MXH;
static Item merge(const Item& l, const Item& r) {
return { l.sum + r.sum, std::min(l.mn, r.mn), std::max(l.mx, r.mx) };
}
};
typedef std::shared_ptr <PNode> PPNode;
Item item;
PPNode lc = nullptr, rc = nullptr;
PNode(const Item& _item) : item(_item) { }
PNode(PPNode _lc, PPNode _rc) : item(Item::merge(_lc->item, _rc->item)), lc(_lc), rc(_rc) { }
static PPNode build(int l, int r) {
if (!(r - l - 1)) return PPNode(new PNode({ }));
int mid = (l + r) >> 1;
return PPNode(new PNode(build(l, mid), build(mid, r)));
}
static PPNode set(PPNode node, int ind, int l, int r) {
if (!(r - l - 1)) return PPNode(new PNode({ 1, ind, ind }));
int mid = (l + r) >> 1;
if (ind < mid) return PPNode(new PNode(set(node->lc, ind, l, mid), node->rc));
return PPNode(new PNode(node->lc, set(node->rc, ind, mid, r)));
}
Item query(int tl, int tr, int l, int r) {
if (l >= tr || r <= tl) return { };
if (l >= tl && r <= tr) return item;
int mid = (l + r) >> 1;
return Item::merge(lc->query(tl, tr, l, mid), rc->query(tl, tr, mid, r));
}
};
int n;
std::vector <int> h;
Sparse sparse;
std::vector <std::shared_ptr <PNode>> pst;
std::map <int, int> smp;
void init(int N, std::vector <int> H) {
n = N + 4;
h = H;
h.insert(h.begin(), { 0, MXH });
h.insert(h.end(), { MXH, 0 });
sparse.init(h);
std::vector <std::pair <int, int>> ord(N);
for (int i = 2; i < n - 2; i++) ord[i - 2] = { h[i], i };
std::sort(ord.begin(), ord.end());
std::set <int> st = { 0, n - 1 };
std::vector <int> tmon(n);
for (auto [hei, i] : ord) {
auto it = st.lower_bound(i);
tmon[i] = std::max(0, std::min(sparse.query(*prev(it) + 1, i - 1).mx, sparse.query(i + 1, *it).mx) - hei);
st.insert(i);
}
smp[MXH] = 0;
pst.push_back(PNode::build(0, 4 * n));
for (int i = 2; i < n - 2; i++) ord[i - 2].first = tmon[i];
std::sort(ord.rbegin(), ord.rend());
for (auto [dv, i] : ord) {
pst.push_back(PNode::set(pst.back(), i, 0, 4 * n));
smp[dv] = (int) pst.size() - 1;
}
}
int max_towers(int L, int R, int D) {
L += 2, R += 2;
std::shared_ptr <PNode> node = pst[smp.lower_bound(D)->second];
PNode::Item pit = node->query(L, R + 1, 0, 4 * n);
int ans = pit.sum;
ans += sparse.query(L, pit.mn).anl >= D;
ans += sparse.query(pit.mx + 1, R + 1).anr >= D;
return ++ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
35340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1232 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1232 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
58728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
14552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1232 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
35340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
