#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define bit(x, i) ((x >> i) & 1)
#define inf 2000'000'000LL
template<typename T>
using vec = vector<T>;
template<typename it>
struct SparseTable {
using T = typename remove_reference<decltype(*declval<it>())>::type;
vector<vector<T>> t;
function<T(T, T)> f;
vector<int> log;
SparseTable() = default;
SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
int n = distance(first, last);
t.assign(32 - __builtin_clz(n), vector<T>(n));
t[0].assign(first, last);
log.resize(n + 1);
for (int i = 2; i <= n; i++)
log[i] = log[i / 2] + 1;
for (int i = 1; i < t.size(); i++)
for (int j = 0; j < n - (1 << i) + 1; j++)
t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
}
T get(int l, int r) {
int h = log[r - l + 1];
return f(t[h][l], t[h][r - (1 << h) + 1]);
}
};
struct node {
int l, r;
int sum;
};
vec<node> nodes;
void fetch(int x) {
int sm = 0;
if (nodes[x].l != -1) {
sm += nodes[nodes[x].l].sum;
}
if (nodes[x].r != -1) {
sm += nodes[nodes[x].r].sum;
}
nodes[x].sum = sm;
}
int new_node() {
nodes.push_back({-1, -1, 0});
return nodes.size() - 1;
}
vec<int> roots;
int build(int tl, int tr) {
if (tl == tr) {
int id = new_node();
nodes[id].sum = 0;
return id;
}
int id = new_node();
int tm = (tl + tr) / 2;
int l = build(tl, tm);
int r = build(tm + 1, tr);
nodes[id].l = l;
nodes[id].r = r;
fetch(id);
return id;
}
int get(int v, int tl, int tr, int l, int r) {
if (tl == l and tr == r) {
return nodes[v].sum;
}
int tm = (tl + tr) / 2;
if (r <= tm) {
return get(nodes[v].l, tl, tm, l, r);
}
if (l > tm) {
return get(nodes[v].r, tm + 1, tr, l, r);
}
return get(nodes[v].l, tl, tm, l, tm) + get(nodes[v].r, tm + 1, tr, tm + 1, r);
}
int update(int v, int tl, int tr, int pos, int x) {
if (tl == tr) {
int id = new_node();
nodes[id].sum = x;
return id;
}
int tm = (tl + tr) / 2;
int id = new_node();
if (pos <= tm) {
int tid = update(nodes[v].l, tl, tm, pos, x);
nodes[id].l = tid;
nodes[id].r = nodes[v].r;
} else {
int tid = update(nodes[v].r, tm + 1, tr, pos, x);
nodes[id].l = nodes[v].l;
nodes[id].r = tid;
}
fetch(id);
return id;
}
vec<int> h;
int n;
vec<pair<int, int>> deltas;
void init(int N, std::vector<int> H) {
n = N;
h = H;
SparseTable stmin(h.begin(), h.end(), [](int a, int b) { return min(a, b); });
SparseTable stmax(h.begin(), h.end(), [](int a, int b) { return max(a, b); });
for (int i = 0; i < n; i++) {
int h1 = inf;
if (i != 0) {
if (stmin.get(0, i - 1) < h[i]) {
int tl = 0;
int tr = i - 1;
while (tl != tr) {
int tm = (tl + tr + 1) / 2;
if (stmin.get(tm, i - 1) < h[i]) {
tl = tm;
} else {
tr = tm - 1;
}
}
h1 = stmax.get(tl, i - 1);
}
}
int h2 = inf;
if (i != n - 1) {
if (stmin.get(i + 1, n - 1) < h[i]) {
int tl = i + 1;
int tr = n - 1;
while (tl != tr) {
int tm = (tl + tr) / 2;
if (stmin.get(i + 1, tm) < h[i]) {
tr = tm;
} else {
tl = tm + 1;
}
}
h2 = stmax.get(i + 1, tr);
}
}
int max_delta = min(h1, h2) - h[i];
deltas.push_back({max_delta, i});
}
sort(deltas.rbegin(), deltas.rend());
int t = build(0, n - 1);
roots.push_back(t);
for (auto [d, i]: deltas) {
t = update(roots.back(), 0, n - 1, i, 1);
roots.push_back(t);
}
}
int max_towers(int L, int R, int D) {
int tl = 0;
int tr = n - 1;
while (tl != tr) {
int tm = (tl + tr) / 2;
if (deltas[tm].first >= D) {
tr = tm;
} else {
tl = tm + 1;
}
}
if (deltas[0].first < D)
tl = -1;
int vr = roots[tl + 1];
int ans = get(vr, 0, n - 1, L, R);
return ans;
}
Compilation message
towers.cpp: In instantiation of 'SparseTable<it>::SparseTable(it, it, std::function<typename std::remove_reference<decltype (* declval<it>())>::type(typename std::remove_reference<decltype (* declval<it>())>::type, typename std::remove_reference<decltype (* declval<it>())>::type)>) [with it = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::remove_reference<decltype (* declval<it>())>::type = int]':
towers.cpp:122:81: required from here
towers.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 1; i < t.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
36044 KB |
1st lines differ - on the 1st token, expected: '1', found: '21740' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
1st lines differ - on the 1st token, expected: '13', found: '49' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
1st lines differ - on the 1st token, expected: '13', found: '49' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
566 ms |
42536 KB |
1st lines differ - on the 1st token, expected: '11903', found: '35960' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
11568 KB |
1st lines differ - on the 1st token, expected: '7197', found: '23881' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
1st lines differ - on the 1st token, expected: '13', found: '49' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
36044 KB |
1st lines differ - on the 1st token, expected: '1', found: '21740' |
| 2 |
Halted |
0 ms |
0 KB |
- |
