#include "towers.h"
#include "bits/stdc++.h"
using namespace std;
struct segtree {
vector<pair<int, int>> tree;
int size;
void init(int n) {
size = 1;
while (size < n) size *= 2;
tree.assign(2 * size, make_pair(0, 0));
}
void upd(int i, pair<int, int> v) {
i += size;
tree[i] = max(tree[i], v);
for (; i > 1; i >>= 1) tree[i >> 1] = max(tree[i], tree[i ^ 1]);
}
pair<int, int> get(int l, int r) {
if (l > r) return make_pair(0, 0);
pair<int, int> res = make_pair(0, 0);
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res;
}
};
int n;
vector<int> a;
segtree sg1, sg2;
const int lg = 17;
vector<vector<int>> jump;
set<pair<int, int>, greater<>> st;
void init(int _n, std::vector<int> _a) {
n = _n;
a = _a;
jump = vector(lg + 1, vector(n, -1));
st.clear();
vector<int> all, v;
for (int i = 0; i < n; i++) {
all.emplace_back(a[i]);
all.emplace_back(a[i] + 1);
}
sort(all.begin(), all.end());
for (int i = 0; i < all.size(); i++) {
if (i > 0 and all[i] == all[i - 1]) continue;
v.emplace_back(all[i]);
}
int z = all.size();
sg1.init(z + 1); sg2.init(z + 1);
for (int i = 0; i < n; i++) {
int pos = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
int pos2 = lower_bound(v.begin(), v.end(), a[i] + 1) - v.begin();
auto it = sg1.get(pos2, z);
if (it.first > 0) jump[0][i] = it.second;
it.second = i;
it.first++;
sg2.upd(pos2, it);
sg1.upd(pos, sg2.get(0, pos));
}
for (int i = 1; i < n; i++) {
if (jump[0][i] == -1) continue;
for (int j = 1; j < lg; j++) {
jump[j][i] = jump[j - 1][jump[j - 1][i]];
if (jump[j][i] == -1) break;
}
}
for (int l = 0, r = 0; r < n; r++) {
if (r == n - 1 or a[r] > a[r + 1]) {
st.emplace(l, r);
l = r + 1;
}
}
}
int max_towers(int l, int r, int d) {
auto it = st.upper_bound(make_pair(r, (int) 1e9));
if (l > it->first) return 1;
int i = it->first, ans = 1;
for (int j = lg - 1; j >= 0; j--) {
if (jump[j][i] < l) continue;
ans += 1 << j;
i = jump[j][i];
}
return ans;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < all.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
346 ms |
10728 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 |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
700 ms |
20536 KB |
29th lines differ - on the 1st token, expected: '9839', found: '9838' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
5260 KB |
1st lines differ - on the 1st token, expected: '7197', found: '8004' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '16' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
346 ms |
10728 KB |
2nd lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
