#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);
}
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);
}
}
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 (arr[L] < arr[L + 1]) {
int st = 0, ed = upidx.size() - 1;
while (st < ed) {
int mid = (st + ed) / 2;
if (upidx[mid] < L) st = mid + 1;
else ed = mid;
}
if (arr[upidx[st]] < arr[L] + D) ans--;
}
if (arr[R] < arr[R - 1]) {
int st = 0, ed = upidx.size() - 1;
while (st < ed) {
int mid = (st + ed) / 2;
if (upidx[mid] > R) ed = mid;
else st = mid + 1;
}
if (arr[upidx[st]] < arr[R] + d) ans--;
}
return ans;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < upidx.size(); i++) {
| ~~^~~~~~~~~~~~~~
towers.cpp:108:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (adj[now.idx][1] < upidx.size()) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
towers.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 0; i < upidx.size(); i++) first[upidx[i]] = 1;
| ~~^~~~~~~~~~~~~~
towers.cpp:124: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]
124 | for (int i = 0; i < Dlist.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
4780 KB |
5th 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 |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
678 ms |
27956 KB |
1st lines differ - on the 1st token, expected: '11903', found: '11904' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
6396 KB |
Output is correct |
| 2 |
Incorrect |
965 ms |
28152 KB |
6th lines differ - on the 1st token, expected: '8440', found: '8439' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
4780 KB |
5th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
