#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 {
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;
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];
}
else cout << now.idx << " " << adj[[now.idx][0]] << "\n";
}
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];
}
else cout << now.idx << " " << adj[[now.idx][0]] << "\n";
}
}
// for (int i = 0; i < Dlist.size(); i++) cout << Dlist[i].first << " " << Dlist[i].second << "\n";
}
int max_towers(int L, int R, int D) {
int ans = Dlist.end() - lower_bound(Dlist.begin(), Dlist.end(), make_pair(D, 0)) + 1;
return ans;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < upidx.size(); i++) {
| ~~^~~~~~~~~~~~~~
towers.cpp:56:41: error: two consecutive '[' shall only introduce an attribute before '[' token
56 | else cout << now.idx << " " << adj[[now.idx][0]] << "\n";
| ^
towers.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (adj[now.idx][1] < upidx.size()) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towers.cpp:67:41: error: two consecutive '[' shall only introduce an attribute before '[' token
67 | else cout << now.idx << " " << adj[[now.idx][0]] << "\n";
| ^
