#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, h[maxn], pref[maxn], peak_pos;
int cnt = 0;
int par[maxn], rnk[maxn];
int find_leader(int v)
{
return (v == par[v]) ? v : par[v] = find_leader(par[v]);
}
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
if (rnk[v] < rnk[u])
swap(v, u);
rnk[v] += rnk[u];
par[u] = v;
}
int dp[maxn], bef[maxn], aft[maxn];
int tree[4 * maxn];
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = h[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int pos, int val)
{
if (left == right)
{
tree[root] = val;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update(root * 2, left, mid, pos, val);
else
update(root * 2 + 1, mid + 1, right, pos, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
int query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return 0;
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return max(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
vector < pair < int, int > > val;
void init(int N, std::vector<int> H)
{
n = N;
for (int i = 0; i < n; i ++)
h[i + 1] = H[i];
for (int i = 1; i <= n; i ++)
if (h[i] > h[i - 1] && h[i] > h[i + 1])
cnt ++;
for (int i = 2; i < n; i ++)
{
pref[i] = pref[i - 1];
if (h[i] > h[i - 1] && h[i] > h[i + 1])
{
pref[i] ++, peak_pos = i;
}
}
build_tree(1, 1, n);
vector < int > st;
st.push_back(0);
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && h[st.back()] >= h[i])
st.pop_back();
bef[i] = st.back();
st.push_back(i);
}
st.clear();
st.push_back(n + 1);
for (int i = n; i > 0; i --)
{
while(!st.empty() && h[st.back()] >= h[i])
st.pop_back();
aft[i] = st.back();
st.push_back(i);
}
for (int i = 1; i <= n; i ++)
{
///cout << bef[i] << " " << aft[i] << endl;
int h1 = 0, h2 = 0;
if (bef[i] != i - 1)
h1 = query(1, 1, n, bef[i] + 1, i - 1);
if (bef[i] == 0)
h1 = 2e9 + 10;
if (aft[i] != i + 1)
h2 = query(1, 1, n, i + 1, aft[i] - 1);
if (aft[i] == n + 1)
h2 = 2e9 + 10;
val.push_back({min(h1, h2) - h[i], i});
///cout << query(1, 1, n, bef[i] + 1)
}
sort(val.begin(), val.end());
//for (int v : val)
// cout << v << " ";
// cout << endl;
}
vector < int > act[maxn];
int max_towers(int L, int R, int D)
{
L ++;
R ++;
int lf = 0, rf = (int)(val.size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (val[mf].first < D)
lf = mf + 1;
else
rf = mf - 1;
}
///vector < int > towers;
int leftmost = n + 1, rightmost = 0, ans = 0;
for (int i = lf; i < val.size(); i ++)
{
if (val[i].second >= L && val[i].second <= R)
{
ans ++;
///towers.push_back(val[i].second);
leftmost = min(leftmost, val[i].second);
rightmost = max(rightmost, val[i].second);
}
}
if (leftmost > rightmost)
{
return 1;
}
int highest_tower = 0;
///cout << leftmost << " " << rightmost << endl;
for (int tower = leftmost - 1; tower >= L; tower --)
{
if (h[tower] + D <= highest_tower &&
highest_tower >= h[leftmost] + D)
{
ans ++;
break;
}
highest_tower = max(highest_tower, h[tower]);
}
for (int tower = rightmost + 1; tower <= R; tower ++)
{
if (h[tower] + D <= highest_tower &&
highest_tower >= h[rightmost] + D)
{
ans ++;
break;
}
highest_tower = max(highest_tower, h[tower]);
}
return ans;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:167:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (int i = lf; i < val.size(); i ++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
5328 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 |
Incorrect |
2 ms |
2640 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4093 ms |
7132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
510 ms |
3792 KB |
25th lines differ - on the 1st token, expected: '464', found: '465' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
5328 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
