#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
using namespace std;
const int MAXN = 100005;
const int K = 300;
struct info {
int v[2];
info() {}
int& operator [](int i) {
return v[i];
}
};
struct leap_info {
int i, c; // start index, count
leap_info() {}
leap_info(int index, int count) {
i = index;
c = count;
}
bool operator < (const leap_info &a) const {
return i < a.i;
}
};
int n;
vector<int> h;
int d;
vector<info> to;
vector<leap_info> leap_to[MAXN / K + 2][K + 2][2];
void init(int N, std::vector<int> H) {
d = -1;
n = N;
h = H;
to.resize(n);
}
void real_init() {
if (OO) {
cout << "begin real_init\n";
}
// prepare edges
vector<int> upper, lower;
for (int i = n - 1; i >= 0; i--) {
while (upper.size() && h[i] > h[upper.back()]) upper.pop_back();
upper.push_back(i);
while (lower.size() && h[i] < h[lower.back()]) lower.pop_back();
lower.push_back(i);
int lo, hi, mid;
lo = -1, hi = (int)upper.size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (h[i] + d <= h[upper[mid]]) lo = mid;
else hi = mid - 1;
}
if (lo == -1) to[i][0] = n;
else to[i][0] = upper[lo];
lo = -1, hi = (int)lower.size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (h[i] - d >= h[lower[mid]]) lo = mid;
else hi = mid - 1;
}
if (lo == -1) to[i][1] = n;
else to[i][1] = lower[lo];
}
if (OO) {
cout << "finished upper lower:\n";
cout << "0:\n";
for (auto &i : to) cout << i[0] << " "; cout << '\n';
cout << "1:\n";
for (auto &i : to) cout << i[1] << " "; cout << '\n';
}
// prepare leaps
for (int chunk = 1; chunk * K < n; chunk++) {
int lim = chunk * K; // [lim, inf) -> [0, K]
vector<info> index(lim), count(lim);
for (int i = lim - 1; i >= 0; i--) {
int last_layer;
if (to[i][0] >= lim) {
index[i][0] = min(to[i][0], lim + K);
count[i][0] = 1;
}
else {
index[i][0] = index[to[i][0]][1];
count[i][0] = 1 + count[to[i][0]][1];
}
last_layer = (0 + count[i][0]) % 2;
leap_to[chunk][index[i][0] - lim][last_layer].emplace_back(i, count[i][0]);
if (to[i][1] >= lim) {
index[i][1] = min(to[i][1], lim + K);
count[i][1] = 1;
}
else {
index[i][1] = index[to[i][1]][0];
count[i][1] = 1 + count[to[i][1]][0];
}
last_layer = (1 + count[i][1]) % 2;
leap_to[chunk][index[i][1] - lim][last_layer].emplace_back(i, count[i][1]);
}
for (int res = 0; res <= K; res++) for (int b = 0; b <= 1; b++) {
for (int i = 1; i < leap_to[chunk][res][b].size(); i++)
if (leap_to[chunk][res][b][i].c < leap_to[chunk][res][b][i - 1].c)
leap_to[chunk][res][b][i].c = leap_to[chunk][res][b][i - 1].c;
reverse(leap_to[chunk][res][b].begin(), leap_to[chunk][res][b].end());
}
}
if (OO) {
cout << "end real_init\n";
}
}
int max_towers(int L, int R, int D) {
if (d == -1) {
d = D;
real_init();
}
int chunk = R / K;
int lim = chunk * K;
int result = 1;
vector<info> count(R - lim + 1);
for (int i = R; i >= lim && i >= L; i--) {
int placei = i - lim;
if (to[i][0] > R)
count[placei][0] = 1;
else
count[placei][0] = max(1, 1 + count[to[i][0] - lim][1]);
if (to[i][1] > R)
count[placei][1] = -1e9; // NOTE: we must end on a minimum
else
count[placei][1] = max(1, 1 + count[to[i][1] - lim][0]);
if (chunk == 0) {
result = max(max(result, count[placei][0]), count[placei][1]);
}
else {
// ends at 0: leap_to[chunk][placei][0]
auto it = lower_bound(leap_to[chunk][placei][0].begin(), leap_to[chunk][placei][0].end(), leap_info(L, 0));
if (it != leap_to[chunk][placei][0].end())
result = max(result, max(0, count[placei][0]) + it->c);
// ends at 1: leap_to[chunk][placei][1]
it = lower_bound(leap_to[chunk][placei][1].begin(), leap_to[chunk][placei][1].end(), leap_info(L, 0));
if (it != leap_to[chunk][placei][1].end())
result = max(result, max(0, count[placei][1]) + it->c);
}
}
if (chunk > 0) {
// also check stuff that exceed R: [R - lim + 1, K]
// make sure we exceed with a maximum
for (int res = R - lim + 1; res <= K; res++) {
auto it = lower_bound(leap_to[chunk][res][1].begin(), leap_to[chunk][res][1].end(), leap_info(L, 0));
if (it != leap_to[chunk][res][1].end())
result = max(result, it->c);
}
}
if (OO) {
cout << "result " << result << '\n';
}
return (result + 1) / 2;
}
Compilation message
towers.cpp: In function 'void real_init()':
towers.cpp:78:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
78 | for (auto &i : to) cout << i[0] << " "; cout << '\n';
| ^~~
towers.cpp:78:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
78 | for (auto &i : to) cout << i[0] << " "; cout << '\n';
| ^~~~
towers.cpp:80:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
80 | for (auto &i : to) cout << i[1] << " "; cout << '\n';
| ^~~
towers.cpp:80:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
80 | for (auto &i : to) cout << i[1] << " "; cout << '\n';
| ^~~~
towers.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<leap_info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i = 1; i < leap_to[chunk][res][b].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
915 ms |
116468 KB |
31st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5072 KB |
1st lines differ - on the 1st token, expected: '13', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5072 KB |
1st lines differ - on the 1st token, expected: '13', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1974 ms |
269636 KB |
1st lines differ - on the 1st token, expected: '11903', found: '8965' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
440 ms |
22492 KB |
1st lines differ - on the 1st token, expected: '7197', found: '5515' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5072 KB |
1st lines differ - on the 1st token, expected: '13', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
915 ms |
116468 KB |
31st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
