#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T, size_t L>
struct max_segtree
{
T t[L << 1];
max_segtree() { fill(t, t + (L << 1), numeric_limits<T>::min()); }
void update(size_t i, T x)
{
i += L;
t[i] = max(t[i], x);
while (i >>= 1)
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
T range_max(size_t i, size_t j)
{
i += L, j += L;
T x = numeric_limits<T>::min();
while (i <= j)
{
if (i & 1)
x = max(x, t[i++]);
if (!(j & 1))
x = max(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
};
template <typename T, size_t L>
struct min_segtree
{
T t[L << 1];
min_segtree() { fill(t, t + (L << 1), numeric_limits<T>::max()); }
void update(size_t i, T x)
{
i += L;
t[i] = min(t[i], x);
while (i >>= 1)
t[i] = min(t[i << 1], t[i << 1 | 1]);
}
T range_min(size_t i, size_t j)
{
i += L, j += L;
T x = numeric_limits<T>::max();
while (i <= j)
{
if (i & 1)
x = min(x, t[i++]);
if (!(j & 1))
x = min(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
};
struct node
{
uint32_t l, r, s;
};
constexpr size_t N = 100000, M = 2000000, L = 1 << 17;
node tree[M];
uint32_t roots[N];
vector<int64_t> delta_coords;
size_t left_greater[N], left_smaller[N], right_greater[N], right_smaller[N], num_nodes;
max_segtree<int64_t, L> hmax;
uint32_t incr(size_t i, uint32_t x, size_t k, size_t a = 0, size_t b = L - 1)
{
uint32_t new_node = num_nodes++;
if (a == b)
{
tree[new_node].s = tree[k].s + x;
return new_node;
}
if (i <= (a + b) >> 1)
{
tree[new_node].r = tree[k].r;
tree[new_node].l = incr(i, x, tree[k].l, a, (a + b) >> 1);
}
else
{
tree[new_node].l = tree[k].l;
tree[new_node].r = incr(i, x, tree[k].r, ((a + b) >> 1) + 1, b);
}
tree[new_node].s = tree[tree[new_node].l].s + tree[tree[new_node].r].s;
return new_node;
}
uint32_t range_sum(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return 0;
if (i <= a && b <= j)
return tree[k].s;
return range_sum(i, j, tree[k].l, a, (a + b) >> 1) +
range_sum(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
}
uint32_t get_root(int64_t delta)
{
return roots[upper_bound(delta_coords.begin(), delta_coords.end(), delta, greater<int64_t>()) - delta_coords.begin() - 1];
}
void init(int n, vector<int> h)
{
{
stack<size_t> s;
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && h[s.top()] < h[i])
s.pop();
left_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && h[s.top()] > h[i])
s.pop();
left_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && h[s.top()] < h[i])
s.pop();
right_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && h[s.top()] > h[i])
s.pop();
right_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
}
for (size_t i = 0; i < n; ++i)
hmax.update(i, h[i]);
vector<pair<int64_t, size_t>> delta;
for (size_t i = 0; i < n; ++i)
{
int64_t d = INT64_MAX;
if (left_smaller[i] != SIZE_MAX)
d = min(d, hmax.range_max(left_smaller[i] + 1, i - 1));
if (right_smaller[i] != SIZE_MAX)
d = min(d, hmax.range_max(i + 1, right_smaller[i] - 1));
if (left_smaller[i] == SIZE_MAX && right_smaller[i] == SIZE_MAX)
delta.emplace_back(INT64_MAX, i);
else if (d != INT64_MIN)
delta.emplace_back((d - h[i]), i);
}
sort(delta.begin(), delta.end(), greater<pair<int64_t, size_t>>());
uint32_t curr_root = 1;
for (size_t i = L - 1; i; --i)
tree[i].l = i << 1, tree[i].r = i << 1 | 1;
for (size_t i = 0, k = 0; i < delta.size();)
{
size_t j = i;
while (j < delta.size() && delta[j].first == delta[i].first)
curr_root = incr(delta[j].second, 1, curr_root), ++j;
roots[k] = curr_root;
delta_coords.push_back(delta[i].first);
i = j;
++k;
}
}
int max_towers(int l, int r, int d)
{
return range_sum(l, r, get_root(d));
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:131:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
131 | for (size_t i = 0; i < n; ++i)
| ~~^~~
towers.cpp:142:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
142 | for (size_t i = 0; i < n; ++i)
| ~~^~~
towers.cpp:153:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
153 | for (size_t i = n - 1; i < n; --i)
| ~~^~~
towers.cpp:164:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
164 | for (size_t i = n - 1; i < n; --i)
| ~~^~~
towers.cpp:173:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
173 | for (size_t i = 0; i < n; ++i)
| ~~^~~
towers.cpp:177:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
177 | for (size_t i = 0; i < n; ++i)
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
306 ms |
6420 KB |
1st lines differ - on the 1st token, expected: '1', found: '7' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3920 KB |
Output is correct |
2 |
Correct |
2 ms |
3920 KB |
Output is correct |
3 |
Correct |
2 ms |
3920 KB |
Output is correct |
4 |
Incorrect |
2 ms |
4028 KB |
1st lines differ - on the 1st token, expected: '336', found: '346' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3920 KB |
Output is correct |
2 |
Correct |
2 ms |
3920 KB |
Output is correct |
3 |
Correct |
2 ms |
3920 KB |
Output is correct |
4 |
Incorrect |
2 ms |
4028 KB |
1st lines differ - on the 1st token, expected: '336', found: '346' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
464 ms |
14624 KB |
1st lines differ - on the 1st token, expected: '11903', found: '1034060969' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
197 ms |
5200 KB |
1st lines differ - on the 1st token, expected: '7197', found: '168009582' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3920 KB |
Output is correct |
2 |
Correct |
2 ms |
3920 KB |
Output is correct |
3 |
Correct |
2 ms |
3920 KB |
Output is correct |
4 |
Incorrect |
2 ms |
4028 KB |
1st lines differ - on the 1st token, expected: '336', found: '346' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
306 ms |
6420 KB |
1st lines differ - on the 1st token, expected: '1', found: '7' |
2 |
Halted |
0 ms |
0 KB |
- |