#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> arr;
vector<int> upidx, downidx;
struct localmax {
int idx, d, l, r;
bool operator<(const localmax &other) const {
if (d == other.d) return idx < other.idx;
return d < other.d;
}
void update() {
d = arr[upidx[idx]] - max(arr[l], arr[r]);
}
} local_value[101010];
int adj[101010][2];
set<localmax> local;
vector< pair<int, int> > Dlist;
struct Node {
Node *lt, *rt;
int val;
Node() {
lt = rt = NULL;
val = 0;
}
};
Node *root[101010];
int first[101010];
void build(Node *node, int st, int ed) {
if (st == ed) {
node->val = first[st];
return;
}
int mid = (st + ed) / 2;
node->lt = new Node();
node->rt = new Node();
build(node->lt, st, mid);
build(node->rt, mid + 1, ed);
node->val = node->lt->val + node->rt->val;
}
void update(Node *prev, Node *now, int st, int ed, int idx, int value) {
if (st == ed) {
now->val = value;
return;
}
int mid = (st + ed) / 2;
if (idx <= mid) {
now->lt = new Node();
now->rt = prev->rt;
update(prev->lt, now->lt, st, mid, idx, value);
}
else {
now->lt = prev->lt;
now->rt = new Node();
update(prev->rt, now->rt, mid + 1, ed, idx, value);
}
now->val = now->lt->val + now->rt->val;
}
int get(Node *node, int st, int ed, int gs, int ge) {
if (st > ge || ed < gs) return 0;
if (gs <= st && ed <= ge) return node->val;
int mid = (st + ed) / 2;
return get(node->lt, st, mid, gs, ge) + get(node->rt, mid + 1, ed, gs, ge);
}
struct minseg {
int tree[101010];
vector<int> initarr;
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = initarr[st];
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
int get(int v, int st, int ed, int gs, int ge) {
if (st > ge || ed < gs) return 2e9;
if (gs <= st && ed <= ge) return tree[v];
int mid = (st + ed) / 2;
return min(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
}
} mintree;
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) arr.push_back(H[i]);
if (arr[0] < arr[1]) downidx.push_back(0);
for (int i = 1; i < n - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) upidx.push_back(i);
if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) downidx.push_back(i);
}
if (arr[n - 1] < arr[n - 2]) downidx.push_back(n - 1);
for (int i = 0; i < upidx.size(); i++) {
local_value[i] = {i, 0, downidx[i], downidx[i + 1]};
local_value[i].update();
local.insert(local_value[i]);
adj[i][0] = i - 1;
adj[i][1] = i + 1;
}
while (!local.empty()) {
localmax now = *local.begin();
Dlist.push_back({now.d, upidx[now.idx]});
int next = (arr[now.l] < arr[now.r] ? now.l : now.r);
local.erase(local.begin());
if (adj[now.idx][0] >= 0) {
set<localmax>::iterator iter = local.find(local_value[adj[now.idx][0]]);
if (iter != local.end()) {
local.erase(iter);
local_value[adj[now.idx][0]].r = next;
local_value[adj[now.idx][0]].update();
local.insert(local_value[adj[now.idx][0]]);
adj[adj[now.idx][0]][1] = adj[now.idx][1];
}
}
if (adj[now.idx][1] < upidx.size()) {
set<localmax>::iterator iter = local.find(local_value[adj[now.idx][1]]);
if (iter != local.end()) {
local.erase(iter);
local_value[adj[now.idx][1]].l = next;
local_value[adj[now.idx][1]].update();
local.insert(local_value[adj[now.idx][1]]);
adj[adj[now.idx][1]][0] = adj[now.idx][0];
}
}
}
for (int i = 0; i < upidx.size(); i++) first[upidx[i]] = 1;
root[0] = new Node();
build(root[0], 0, n - 1);
for (int i = 0; i < Dlist.size(); i++) {
root[i + 1] = new Node();
update(root[i], root[i + 1], 0, n - 1, Dlist[i].second, 0);
}
mintree.initarr = arr;
mintree.init(1, 0, n - 1);
}
int max_towers(int L, int R, int D) {
int d = lower_bound(Dlist.begin(), Dlist.end(), make_pair(D, 0)) - Dlist.begin();
int ans = get(root[d], 0, n - 1, L, R) + 1;
if (ans > 1) {
int st = L, ed = R;
while (st < ed) {
int mid = (st + ed) / 2;
if (get(root[d], 0, n - 1, L, mid) > 0) ed = mid;
else st = mid + 1;
}
//cout << st << " " << mintree.get(1, 0, n - 1, L, st - 1) << "\n";
if (mintree.get(1, 0, n - 1, L, st - 1) + D > arr[st]) ans--;
st = L, ed = R;
while (st < ed) {
int mid = (st + ed + 1) / 2;
if (get(root[d], 0, n - 1, mid, R) > 0) st = mid;
else ed = mid - 1;
}
//cout << st << " " << mintree.get(1, 0, n - 1, st + 1, R) << "\n";
if (mintree.get(1, 0, n - 1, st + 1, R) + D > arr[st]) ans--;
}
return ans;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i = 0; i < upidx.size(); i++) {
| ~~^~~~~~~~~~~~~~
towers.cpp:130:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | if (adj[now.idx][1] < upidx.size()) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towers.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 0; i < upidx.size(); i++) first[upidx[i]] = 1;
| ~~^~~~~~~~~~~~~~
towers.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0; i < Dlist.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
10572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
720 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
720 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
119 ms |
57804 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
517 ms |
6836 KB |
Output is correct |
| 2 |
Runtime error |
122 ms |
58376 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
720 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
10572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
