#include "towers.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
struct MSTree {
int n, N;
typedef map<int, int, greater<int>> Entry;
vector<Entry> tree;
MSTree() = default;
MSTree(const vi& values) {
n = values.size();
N = 1;
while (N < n) N *= 2;
tree = vector<Entry>(2 * N);
loop(i, n) {
tree[N + i] = {{values[i], 1}, { 0, 0 }};
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
}
Entry merge(const Entry& a, const Entry& b) {
Entry out;
auto it1 = a.begin();
auto it2 = b.begin();
int pref1 = 0;
int pref2 = 0;
while (it1 != a.end() && it2 != b.end()) {
if (it1->first > it2->first) {
pref1 = it1->second;
out[it1->first] = pref1 + pref2;
it1++;
}
else {
pref2 = it2->second;
out[it2->first] = pref1 + pref2;
it2++;
}
}
while (it1 != a.end()) {
pref1 = it1->second;
out[it1->first] = pref1 + pref2;
it1++;
}
while (it2 != b.end()) {
pref2 = it2->second;
out[it2->first] = pref1 + pref2;
it2++;
}
return out;
}
int range(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) tr = N;
if (l <= tl && r >= tr) {
auto it = tree[i].upper_bound(v);
if (it == tree[i].begin())
return 0;
return (--it)->second;
}
if (tl >= r || tr <= l) {
return 0;
}
int tm = (tl + tr) / 2;
return range(l, r, v, i * 2, tl, tm) + range(l, r, v, i * 2 + 1, tm, tr);
}
int leftMost(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) tr = N;
if (tl >= r || tr <= l) {
return -1;
}
if (tr - tl == 1) {
auto it = tree[i].upper_bound(v);
if (it == tree[i].begin())
return -1;
return tl;
}
int tm = (tl + tr) / 2;
int val1 = leftMost(l, r, v, i * 2, tl, tm);
if (val1 >= 0)
return val1;
return leftMost(l, r, v, i * 2 + 1, tm, tr);
}
int rightMost(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) tr = N;
if (tl >= r || tr <= l) {
return -1;
}
if (tr - tl == 1) {
auto it = tree[i].upper_bound(v);
if (it == tree[i].begin())
return -1;
return tl;
}
int tm = (tl + tr) / 2;
int val1 = rightMost(l, r, v, i * 2 + 1, tm, tr);
if (val1 >= 0)
return val1;
return rightMost(l, r, v, i * 2, tl, tm);
}
};
struct SparseTable {
int n;
vii table[17];
vi values;
SparseTable(const vi& _values) {
n = _values.size();
values = _values;
table[0] = vii(n);
for (int i = 0; i < n; i++) {
table[0][i] = { i, i };
}
for (int pow = 1; pow < 17; pow++) {
if (n - (1 << pow) + 1 <= 0)
break;
table[pow] = vii(n - (1 << pow) + 1);
for (int i = 0; i + (1 << pow) <= n; i++) {
ii v1 = table[pow - 1][i];
ii v2 = table[pow - 1][i + (1 << pow) / 2];
if (values[v1.first] < values[v2.first]) {
table[pow][i].first = v1.first;
}
else {
table[pow][i].first = v2.first;
}
if (values[v1.second] > values[v2.second]) {
table[pow][i].second = v1.second;
}
else {
table[pow][i].second = v2.second;
}
}
}
}
int minIdx(int l, int r) {
int exp = 0;
while ((1 << exp) * 2 <= r - l + 1)
exp++;
int pow = 1 << exp;
ii v1 = table[exp][l];
ii v2 = table[exp][r - pow + 1];
if (values[v1.first] < values[v2.first]) {
return v1.first;
}
else {
return v2.first;
}
}
int maxIdx(int l, int r) {
int exp = 0;
while ((1 << exp) * 2 <= r - l + 1)
exp++;
int pow = 1 << exp;
ii v1 = table[exp][l];
ii v2 = table[exp][r - pow + 1];
if (values[v1.second] > values[v2.second]) {
return v1.second;
}
else {
return v2.second;
}
}
};
int n;
vi h;
vi bestD, bestLeftD, bestRightD;
MSTree allD, leftD, rightD;
void init(int N, std::vector<int> H) {
//all H[i] are different
//dp[i] = max of 1 and all dp[j] over j s.t. j < i && maxH(j, i) - D >= max(H[i], H[j])
//D = 1
//H = 1, 2, 6, 4, 5, 3, 7
//dp= 1, 1, 1, 2, 2, 3, 1
//count no. of i for which there exist l, r such that h[i] = minH[l, r] && h[i] + D <= h[l], h[r]
n = N;
h = H;
if (n == 1) return;
SparseTable sparse(H);
sparse.minIdx(1, 1);
bestD = vi(n), bestLeftD = vi(n), bestRightD = vi(n);
loop(i, n) {
int minLeft, minRight;
{
int l = -1, r = i - 1;
while (l < r) {
int m = (l + r + 1) / 2;
int minIdx = sparse.minIdx(m, r);
if (h[minIdx] < h[i]) {
l = m;
}
else {
r = m - 1;
}
}
minLeft = l;
}
{
int l = i + 1, r = n;
while (l < r) {
int m = (l + r) / 2;
int minIdx = sparse.minIdx(l, m);
if (h[minIdx] < h[i]) {
r = m;
}
else {
l = m + 1;
}
}
minRight = r;
}
cout << i << ' ' << minLeft << ' ' << minRight << endl;
if (minLeft + 1 <= i - 1 && minRight - 1 >= i + 1) {
bestD[i] = min(h[sparse.maxIdx(minLeft + 1, i - 1)], h[sparse.maxIdx(i + 1, minRight - 1)]) - h[i];
}
if (minRight - 1 >= i + 1) {
bestLeftD[i] = h[sparse.maxIdx(i + 1, minRight - 1)] - h[i];
}
if (minLeft + 1 <= i - 1) {
bestRightD[i] = h[sparse.maxIdx(minLeft + 1, i - 1)] - h[i];
}
}
allD = MSTree(bestD);
leftD = MSTree(bestLeftD);
rightD = MSTree(bestRightD);
}
int max_towers(int L, int R, int D) {
if (L == R) {
return 1;
}
int left = leftD.leftMost(L, R + 1, D);
int right = rightD.rightMost(L, R + 1, D);
if (left == -1 || right == -1 || left + 1 > right - 1) {
return 1;
}
int extra = allD.range(left + 1, right - 1 + 1, D);
return 2 + extra;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9048 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
15192 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
3672 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9048 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
