#include "towers.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 20;
const int INF = 1e9;
int n;
int h[MAXN];
int perm[MAXN];
int getLog[MAXN];
struct Valley
{
int idx;
int left;
int right;
};
struct SparseMAX
{
int sparse[MAXLOG][MAXN];
void build(const std::vector <int> &vals)
{
for (int i = 0 ; i < vals.size() ; ++i)
{
sparse[0][i] = vals[i];
}
for (int log = 1 ; (1 << log) < vals.size() ; ++log)
{
for (int i = 0 ; i + (1 << log) - 1 < vals.size() ; ++i)
{
sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
}
}
for (int i = 1 ; i <= vals.size() ; ++i)
{
getLog[i] = getLog[i - 1];
if ((1 << getLog[i] + 1) < i) getLog[i]++;
}
}
inline int findMAX(int l, int r)
{
int log = getLog[r - l + 1];
return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
}
};
std::vector <Valley> valleys;
struct MergeSortTree
{
std::vector <int> tree[4*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].push_back(std::min(valleys[l].left, valleys[l].right));
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node].reserve(r - l + 1);
int lp = l, rp = mid + 1;
for (int pos = l ; pos <= r ; ++pos)
{
if (lp == mid + 1)
{
tree[node].push_back(tree[2*node + 1][rp++]);
continue;
}
if (rp == r + 1)
{
tree[node].push_back(tree[2*node][lp++]);
continue;
}
if (tree[2*node][lp] > tree[2*node + 1][rp])
{
tree[node].push_back(tree[2*node][lp++]);
continue;
} else
{
tree[node].push_back(tree[2*node + 1][rp++]);
continue;
}
}
}
inline int findBigger(int node, int value)
{
int l = -1, r = tree[node].size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (tree[node][mid] >= value) l = mid;
else r = mid;
}
return l + 1;
}
int query(int l, int r, int node, int queryL, int queryR, int queryVal)
{
if (queryL <= l && r <= queryR)
{
return findBigger(node, queryVal);
}
int ans = 0;
int mid = (l + r) / 2;
if (queryL <= mid) ans += query(l, mid, 2*node, queryL, queryR, queryVal);
if (mid + 1 <= queryR) ans += query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
return ans;
}
void build()
{
build(0, valleys.size() - 1, 1);
}
int query(int l, int r, int val)
{
return query(0, valleys.size() - 1, 1, l, r, val);
}
};
MergeSortTree tree;
int nextPeak[MAXN];
int prevPeak[MAXN];
bool isValley[MAXN];
int nextValley[MAXN];
int prevValley[MAXN];
SparseMAX leftMAX, rightMAX;
std::vector <int> extremums;
std::vector <int> peaks;
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 (i == 1 || i == n || (h[i] < h[i - 1] && h[i] < h[i + 1])) extremums.push_back(i);
else if (h[i] > h[i - 1] && h[i] > h[i + 1]) extremums.push_back(i);
}
for (int i = 0 ; i < extremums.size() ; ++i)
{
if (h[extremums[i]] > h[extremums[i] - 1] && h[extremums[i]] > h[extremums[i] + 1])
{
peaks.push_back(extremums[i]);
continue;
}
int left = INF;
int right = INF;
if (i != 0) left = h[extremums[i - 1]] - h[extremums[i]];
if (i != extremums.size() - 1) right = h[extremums[i + 1]] - h[extremums[i]];
valleys.push_back({extremums[i], left, right});
isValley[extremums[i]] = true;
}
std::fill(nextPeak + 1, nextPeak + 1 + n, -1);
std::fill(prevPeak + 1, prevPeak + 1 + n, -1);
std::fill(prevValley + 1, prevValley + 1 + n, -1);
std::fill(nextValley + 1,nextValley + 1 + n, -1);
int ptr = 1;
for (int i = 0 ; i < valleys.size() ; ++i)
{
while (ptr < valleys[i].idx)
{
nextValley[ptr++] = i;
}
}
ptr = 1;
for (int i = 0 ; i < peaks.size() ; ++i)
{
while (ptr <= peaks[i])
{
nextPeak[ptr++] = i;
}
}
ptr = n;
for (int i = valleys.size() - 1 ; i >= 0 ; --i)
{
while (ptr > valleys[i].idx)
{
prevValley[ptr--] = i;
}
}
ptr = n;
for (int i = peaks.size() - 1 ; i >= 0 ; --i)
{
while (ptr >= peaks[i])
{
prevPeak[ptr--] = i;
}
}
// std::cout << "valleys\n";
// for (const Valley &v : valleys)
// {
// std::cout << v.idx << ' ';
// }
// std::cout << '\n';
// std::cout << "diffs\n";
// for (const Valley &v : valleys)
// {
// std::cout << v.left << ' ' << v.right << '\n';
// }
// std::cout << "peaks\n";
// for (const int &idx : peaks)
// {
// std::cout << idx << ' ';
// }
// std::cout << '\n';
std::vector <int> curr;
for (const Valley &v : valleys)
{
curr.push_back(v.left);
}
leftMAX.build(curr);
curr.clear();
for (const Valley &v : valleys)
{
curr.push_back(v.right);
}
rightMAX.build(curr);
tree.build();
}
inline int findFirstRight(int from, int to, int d)
{
int l = from - 1, r = to, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (rightMAX.findMAX(from, mid) < d) l = mid;
else r = mid;
}
return r;
}
inline int findLastLeft(int from, int to, int d)
{
int l = from, r = to + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (leftMAX.findMAX(mid, to) >= d) l = mid;
else r = mid;
}
return l;
}
int max_towers(int l, int r, int d)
{
l++; r++;
// std::cout << "l, r: " << l << ' ' << r << '\n';
// std::cout << "here: " << nextPeak[l] << ' ' << nextPeak[r] << '\n';
// std::cout << "here: " << nextValley[l] << ' ' << prevValley[r] << '\n';
if (nextPeak[l] == nextPeak[r])
{
return 1;
}
int first = nextValley[l];
int last = prevValley[r];
// std::cout << "first last: " << first << ' ' << last << '\n';
int borderL = -1;
int borderR = -1;
int answer = 0;
if (h[l] < h[l + 1] && h[peaks[nextPeak[l]]] - h[l] >= d)
{
// std::cout << "L good\n";
borderL = first;
answer++;
}
if (h[r] < h[r - 1] && h[peaks[prevPeak[r]]] - h[r] >= d)
{
// std::cout << "R good\n";
borderR = last;
answer++;
}
if (borderL == -1)
{
borderL = findFirstRight(first, last, d);
if (valleys[borderL].right < d) return 1;
borderL++;
answer++;
}
if (borderR == -1)
{
borderR = findLastLeft(first, last, d);
if (valleys[borderR].left < d) return 1;
borderR--;
answer++;
}
// std::cout << "borders: " << borderL << ' ' << borderR << '\n';
if (borderL <= borderR)
{
answer += tree.query(borderL, borderR, d);
}
return answer;
}
Compilation message
towers.cpp: In member function 'void SparseMAX::build(const std::vector<int>&)':
towers.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0 ; i < vals.size() ; ++i)
| ~~^~~~~~~~~~~~~
towers.cpp:36:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int log = 1 ; (1 << log) < vals.size() ; ++log)
| ~~~~~~~~~~~^~~~~~~~~~~~~
towers.cpp:38:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0 ; i + (1 << log) - 1 < vals.size() ; ++i)
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
towers.cpp:40:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
40 | sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
| ~~~~^~~
towers.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 1 ; i <= vals.size() ; ++i)
| ~~^~~~~~~~~~~~~~
towers.cpp:47:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
47 | if ((1 << getLog[i] + 1) < i) getLog[i]++;
| ~~~~~~~~~~^~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:164:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int i = 0 ; i < extremums.size() ; ++i)
| ~~^~~~~~~~~~~~~~~~~~
towers.cpp:175:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | if (i != extremums.size() - 1) right = h[extremums[i + 1]] - h[extremums[i]];
| ~~^~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:186:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Valley>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for (int i = 0 ; i < valleys.size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
towers.cpp:195:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int i = 0 ; i < peaks.size() ; ++i)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
436 ms |
11344 KB |
2nd lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9808 KB |
1st lines differ - on the 1st token, expected: '13', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9808 KB |
1st lines differ - on the 1st token, expected: '13', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
35908 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
23504 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9808 KB |
1st lines differ - on the 1st token, expected: '13', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
436 ms |
11344 KB |
2nd lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
