#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
typedef long long ll;
using namespace std;
struct info {
int len[2][2];
int l, r;
info(int x = -1, int i = 0) {
len[0][0] = len[1][1] = -1e9;
len[0][1] = len[1][0] = -1e9;
l = 1e9, r = -1e9;
if (x == 0) {
l = r = i;
len[0][0] = 1;
}
if (x == 1) {
l = r = i;
len[1][1] = 1;
}
}
info operator * (const info &a) const {
info res;
res.l = min(l, a.l);
res.r = max(r, a.r);
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
res.len[i][j] = max(max(res.len[i][j], len[i][j]), a.len[i][j]);
}
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
res.len[i][k] = max(res.len[i][k], len[i][j] + a.len[1 ^ j][k]);
}
return res;
}
void print() {
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
cout << i << " -> " << j << ": " << len[i][j] << '\n';
}
}
};
struct node {
vector<pair<int, info>> data;
node() {
data.emplace_back(0, info());
}
void add(int tim, info i) {
if (data.size() && data.back().first == tim)
data.back().second = i;
else
data.emplace_back(tim, i);
}
info& get(int tim) {
tim = max(tim, 0);
int lo = 0, hi = (int)data.size() - 1, mid;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (data[mid].first <= tim) lo = mid;
else hi = mid - 1;
}
return data[lo].second;
}
};
struct segtree {
int n;
int tim;
vector<node> t;
vector<pair<int, int>> range;
segtree() {}
segtree(int sz) {
tim = 0;
n = max(2, sz);
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n, node());
}
void advance_time(int newtim) {
tim = max(tim, newtim);
}
void fix(int x) {
t[x].add(tim, t[2 * x + 1].get(tim) * t[2 * x + 2].get(tim));
}
void upd(int x, int val) {
if (OO) cout << "upd " << x << " " << val << '\n';
x += n - 1;
t[x].add(tim, info(val, x - (n - 1)));
while (x) {
x = (x - 1) / 2;
fix(x);
}
}
int is_alive(int i, int T) {
info tmp = t[i + n - 1].get(T);
if (tmp.len[0][0] == 1 || tmp.len[1][1] == 1) return 1;
return 0;
}
info query(int l, int r, int T) {
if (l > r) return info();
return query(l, r, T, 0, 0, n - 1);
}
info query(int l, int r, int T, int node, int nl, int nr) {
if (nr < l || r < nl) return info();
if (l <= nl && nr <= r) return t[node].get(T);
int mid = (nl + nr) / 2;
return query(l, r, T, 2 * node + 1, nl, mid) * query(l, r, T, 2 * node + 2, mid + 1, nr);
}
};
struct sptable {
int n;
vector<int> a;
vector<int> mn, mx;
sptable() {}
sptable(const vector<int> &b) {
a = b;
n = max(2, (int)a.size());
while (n != (n & -n)) n += (n & -n);
mn.resize(2 * n);
mx.resize(2 * n);
for (int i = 0; i < a.size(); i++)
mn[i + n - 1] = mx[i + n - 1] = a[i];
for (int i = n - 2; i >= 0; i--)
mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]), mx[i] = max(mx[2 * i + 1], mx[2 * i + 2]);
}
pair<int, int> query(int l, int r) {
if (l > r) return{ 1e9, -1e9 };
int mnres = 1e9, mxres = -1e9;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) {
mnres = min(mnres, mn[l]);
mxres = max(mxres, mx[l]);
l++;
}
if (r & 1) {
mnres = min(mnres, mn[r]);
mxres = max(mxres, mx[r]);
r--;
}
}
if (l == r) {
mnres = min(mnres, mn[l]);
mxres = max(mxres, mx[l]);
}
return{ mnres, mxres };
}
};
struct superset {
int n;
vector<int> a;
set<int> ind;
set<pair<int, int>> q;
superset() {}
superset(const vector<int> &b) {
a = b;
n = a.size();
for (int i = 0; i < n; i++)
ind.insert(i);
for (int i = 0; i < n; i++)
q.emplace(abs(a[i] - a[i + 1]), i);
}
set<pair<int, int>>::iterator getq_element(set<int>::iterator it) {
// assuming it exists
return q.lower_bound(pair<int, int>(abs(a[*it] - a[*next(it)]), *it));
}
int upto(int R) {
auto it = ind.upper_bound(R);
if (it == ind.begin()) return -1;
return *prev(it);
}
int atleast(int L) {
auto it = ind.lower_bound(L);
if (it == ind.end()) return 1e9;
return *it;
}
// data kept between exchanges
int last_min;
set<int>::iterator last_i, last_j, last_k;
int size() {
return ind.size();
}
int get_min() {
return last_min = q.begin()->first;
}
void get_triple() {
auto p = *q.begin();
auto it = ind.lower_bound(p.second);
if (it == ind.begin())
last_i = it;
else
last_i = prev(it);
last_j = next(last_i);
last_k = next(last_j);
}
void remove(int &removed_index, int &i, int &j) {
int mx = max(max(a[*last_i], a[*last_j]), a[*last_k]);
int mn = min(min(a[*last_i], a[*last_j]), a[*last_k]);
int median = (ll)a[*last_i] + (ll)a[*last_j] + (ll)a[*last_k] - mn - mx;
set<int>::iterator it;
if (median == a[*last_i]) it = last_i;
else if (median == a[*last_j]) it = last_j;
else it = last_k;
removed_index = *it;
if (it == ind.begin()) i = -1;
else i = *prev(it);
if (next(it) == ind.end()) j = -1;
else j = *next(it);
// update q
if (i == -1) {
q.erase(getq_element(it));
}
else if (j == -1) {
q.erase(getq_element(prev(it)));
}
else {
q.erase(getq_element(prev(it)));
q.erase(getq_element(it));
q.insert(pair<int, int>(abs(a[i] - a[j]), i));
}
// update ind
ind.erase(it);
}
};
int n;
vector<int> h;
superset ind;
segtree T;
sptable table;
void init(int N, std::vector<int> H) {
n = N;
h = H;
ind = superset(h);
T = segtree(n);
table = sptable(h);
for (int i = 0; i + 1 < n; i++)
if (h[i] < h[i + 1])
T.upd(i, 0);
else
T.upd(i, 1);
while (ind.size() > 2) {
int d = ind.get_min();
T.advance_time(d);
ind.get_triple();
int index, li, ri;
ind.remove(index, li, ri);
T.upd(index, -1);
if (li != -1) {
if (ri == -1) {
T.upd(li, -1);
}
else {
if (h[li] < h[ri])
T.upd(li, 0);
else
T.upd(li, 1);
}
}
if (OO) {
cout << "at d = " << d << ", remove li ri " << index << " " << li << " " << ri << '\n';
}
}
}
int bruteforce(int l, int r, int d) {
int len = r - l + 1;
int best = 0;
for (int mask = 0; mask < (1 << len); mask++) {
vector<int> val;
for (int i = l; i <= r; i++) {
if (mask & (1 << (i - l)))
val.push_back(h[i]);
}
if (val.size() % 2 == 0) continue;
bool good = true;
for (int i = 0; i + 1 < val.size(); i++) {
if (i % 2 == 0 && val[i] + d > val[i + 1]) good = false;
if (i % 2 == 1 && val[i] - d < val[i + 1]) good = false;
}
if (good)
best = max(best, (int)val.size() / 2 + 1);
}
return best;
}
int max_towers(int L, int R, int D) {
int tim = D - 1;
// fix L, R
info q = T.query(L, R, tim);
int l = q.l;
int r = q.r;
if (OO) {
cout << "l r " << l << " " << r << '\n';
}
// break into cases - and also don't forget to consider the boundaries
if (r < l) {
// nothing in between - this is a monotonic range
return 1;
}
q = T.query(l, r - 1, tim);
if (OO) {
cout << "from query received:\n";
q.print();
}
if (L < l) {
// consider left boundary
info boundary = info();
auto pa = table.query(L, l - 1);
if (pa.first + D <= h[l])
boundary = info(0);
else if (pa.second - D >= h[l])
boundary = info(1);
q = boundary * q;
}
if (r < R) {
// consider right boundary
info boundary = info();
auto pa = table.query(r + 1, R);
if (h[r] - D >= pa.first)
boundary = info(1);
else if (h[r] + D <= pa.second)
boundary = info(0);
q = q * boundary;
}
return max(1, q.len[0][1] / 2 + 1);
}
Compilation message
towers.cpp: In constructor 'sptable::sptable(const std::vector<int>&)':
towers.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
towers.cpp: In function 'int bruteforce(int, int, int)':
towers.cpp:282:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
282 | for (int i = 0; i + 1 < val.size(); i++) {
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
387 ms |
87024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
713 ms |
148388 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
19928 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
387 ms |
87024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
