#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int nLeft;
int nRight;
int l, r, sum, minPos, maxPos, minVal;
Node(){};
Node(int _l, int _r, int val) {
nLeft = nRight = -1;
l = _l;
r = _r;
sum = 0;
minPos = 1e9;
maxPos = -1e9;
minVal = val;
assert(l <= r);
}
};
int cntNode;
Node nodes[2000000];
int newNode(int l, int r, int val) {
int id = cntNode;
nodes[id] = Node(l, r, val);
++cntNode;
return id;
}
int mergeNode(int a, int b) {
assert(nodes[a].r + 1 == nodes[b].l);
int res = newNode(nodes[a].l, nodes[b].r, 1e9);
nodes[res].nLeft = a;
nodes[res].nRight = b;
nodes[res].sum = nodes[a].sum + nodes[b].sum;
nodes[res].minPos = min(nodes[a].minPos, nodes[b].minPos);
nodes[res].maxPos = max(nodes[a].maxPos, nodes[b].maxPos);
nodes[res].minVal = min(nodes[a].minVal, nodes[a].minVal);
return res;
}
int build(int l, int r, const vector<int>& h, const vector<bool>& mark) {
if (l == r) {
int n = newNode(l, r, h[l]);
if (mark[l]) {
nodes[n].sum = 1;
nodes[n].minPos = nodes[n].maxPos = l;
}
return n;
}
int mid = (l + r) >> 1;
return mergeNode(build(l, mid, h, mark), build(mid + 1, r, h, mark));
}
int update(int n, int pos) {
assert(n != -1);
if (pos < nodes[n].l || nodes[n].r < pos) {
return n;
}
if (nodes[n].l == nodes[n].r) {
assert(nodes[n].sum == 1);
return newNode(nodes[n].l, nodes[n].r, nodes[n].minVal);
}
return mergeNode(update(nodes[n].nLeft, pos), update(nodes[n].nRight, pos));
}
int getMin(int n, int l, int r) {
assert(n != -1);
if (r < nodes[n].l || nodes[n].r < l) {
return 1e9;
}
if (l <= nodes[n].l && nodes[n].r <= r) {
return nodes[n].minVal;
}
return min(getMin(nodes[n].nLeft, l, r), getMin(nodes[n].nRight, l, r));
}
void get(int n, int l, int r, int &x, int &y, int &sum) {
if (r < nodes[n].l || nodes[n].r < l) {
return;
}
if (l <= nodes[n].l && nodes[n].r <= r) {
sum += nodes[n].sum;
x = min(x, nodes[n].minPos);
y = max(y, nodes[n].maxPos);
return;
}
get(nodes[n].nLeft, l, r, x, y, sum);
get(nodes[n].nRight, l, r, x, y, sum);
}
int n;
vector<int> h;
vector<int> type, changingPoint;
vector<int> roots;
void init(int _n, vector<int> _h) {
n = _n;
h = _h;
set<int> s;
s.insert(0);
for (int i = 1; i < n; ++i) {
if (s.size() & 1) {
if (h[i] > h[*s.rbegin()]) {
s.insert(i);
} else {
s.erase(*s.rbegin());
s.insert(i);
}
} else {
if (h[i] < h[*s.rbegin()]) {
s.insert(i);
} else {
s.erase(*s.rbegin());
s.insert(i);
}
}
}
if (s.size() % 2 == 0) {
s.erase(*s.rbegin());
}
//for (auto x : s) {
//cerr << x << ' ';
//}
//cerr << endl;
vector<bool> mark(n, false);
for (auto x : s) {
mark[x] = true;
}
changingPoint.push_back(0);
roots.push_back(build(0, n - 1, h, mark));
priority_queue<array<int, 3>> pq;
type.assign(n, -1);
int pre = -1, t = 0;
for (int cur : s) {
type[cur] = t;
t ^= 1;
if (pre != -1) {
pq.push({-abs(h[pre] - h[cur]), pre, cur});
}
pre = cur;
}
int last = 0;
while (!pq.empty()) {
auto [d, l, r] = pq.top();
pq.pop();
if (!mark[l] || !mark[r]) {
continue;
}
d = -d;
if (d != last) {
changingPoint.push_back(d);
roots.push_back(roots.back());
last = d;
}
int a[5] = {-1, -1, -1, -1, -1};
if (h[l] > h[r]) {
a[1] = l;
a[2] = r;
auto it = s.lower_bound(l);
if (it != s.begin()) {
a[0] = *(--it);
}
it = s.lower_bound(r);
++it;
if (it != s.end()) {
a[3] = *it;
++it;
}
if (it != s.end()) {
a[4] = *it;
++it;
}
} else {
a[2] = l;
a[3] = r;
auto it = s.lower_bound(l);
if (it != s.begin()) {
a[1] = *(--it);
}
if (it != s.begin()) {
a[0] = *(--it);
}
it = s.lower_bound(r);
++it;
if (it != s.end()) {
a[4] = *it;
++it;
}
}
roots.back() = update(roots.back(), a[2]);
mark[a[2]] = false;
s.erase(a[2]);
if (h[a[1]] == -1 || h[a[3]] == -1) {
if (mark[a[1]]) {
roots.back() = update(roots.back(), a[1]);
mark[a[1]] = false;
s.erase(a[1]);
}
if (mark[a[3]]) {
roots.back() = update(roots.back(), a[3]);
mark[a[3]] = false;
s.erase(a[3]);
}
} else {
if (h[a[1]] > h[a[3]]) {
roots.back() = update(roots.back(), a[3]);
mark[a[3]] = false;
s.erase(a[3]);
pq.push({-abs(h[a[1]] - h[a[4]]), a[1], a[4]});
} else {
roots.back() = update(roots.back(), a[1]);
mark[a[1]] = false;
s.erase(a[1]);
pq.push({-abs(h[a[0]] - h[a[3]]), a[0], a[3]});
}
}
//cerr << "change " << d << ' ' << l << ' ' << r << endl;
for (int i = 0; i < 5; ++i) {
//cerr << a[i] << ' ';
}
//cerr << endl;
}
}
int max_towers(int l, int r, int d) {
int root = roots[lower_bound(changingPoint.begin(), changingPoint.end(), d) - changingPoint.begin() - 1];
int x = 1e9, y = -1e9, res = 0;
get(root, l, r, x, y, res);
if (x > y) {
return 1;
}
assert(type[x] != -1 && type[y] != -1);
if (type[x] == 1) {
if (h[x] - d >= getMin(root, l, x - 1)) {
++res;
} else {
--res;
}
}
if (type[y] == 1) {
if (h[y] - d >= getMin(root, y + 1, r)) {
++res;
} else {
--res;
}
}
//cerr << "query " << l << ' ' << r << ' ' << d << ' ' << res << endl;
return max(1, (res + 1) / 2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
9868 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
44972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
9200 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
9868 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
