#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>H;
struct ST
{
int l, r;
ST *left, *right;
int mn;
pair<int, int> mni;
pair<int, int> mxi;
ST() {}
ST(int l, int r): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2);
right = new ST((l + r) / 2 + 1, r);
mn = min(left->mn, right->mn);
mni = min(left->mni, right->mni);
mxi = max(left->mxi, right->mxi);
}
else
{
left = right = NULL;
mn = H[l];
mni = mxi = {H[l], l};
}
}
int get(int x, int y)
{
if (x <= l && r <= y)
return mn;
if (r < x || y < l)
return 2e9;
return min(left->get(x, y), right->get(x, y));
}
pair<int, int> getmx(int x, int y)
{
if (x <= l && r <= y)
return mxi;
if (r < x || y < l)
return { -2e9, 0};
return max(left->getmx(x, y), right->getmx(x, y));
}
pair<int, int> getmn(int x, int y)
{
if (x <= l && r <= y)
return mni;
if (r < x || y < l)
return { 2e9, 0};
return min(left->getmn(x, y), right->getmn(x, y));
}
} medis;
vector<vector<pair<int, int>>>Fl, Fr;
int N;
vector<int>prv;
vector<int>nxt;
void init(int N_, vector<int> H_) {
N = N_;
H = H_;
prv = vector<int>(N, -1);
nxt = vector<int>(N, N + 1);
{
vector<int>A;
for (int i = 0; i < N; i++)
{
while (!A.empty() && H[A.back()] <= H[i])
A.pop_back();
if (!A.empty())
prv[i] = A.back();
A.push_back(i);
}
A.clear();
for (int i = N - 1; i >= 0; i--)
{
while (!A.empty() && H[A.back()] <= H[i])
A.pop_back();
if (!A.empty())
nxt[i] = A.back();
A.push_back(i);
}
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int a, int b) {return H[a] > H[b];});
set<int>X;
medis = ST(0, N - 1);
auto get = [&](int l, int r)
{
if (l + 1 >= r)
return -1;
int h = medis.get(l + 1, r - 1);
return max(0, min(H[l] - h, H[r] - h));
};
map<int, vector<pair<int, int>>>L;
map<int, vector<pair<int, int>>>R;
auto add = [&](int l, int r, int d, int w)
{
R[d].push_back({r, w});
L[d].push_back({l, w});
};
for (int i : p)
{
int r = -1, l = -1;
auto it = X.lower_bound(i);
if (it != X.end())
{
r = *it;
}
if (it != X.begin())
{
it--;
l = *it;
}
X.insert(i);
if (l == -1 || r == -1)
{
if (r != -1 && i + 1 < r)
add(i, r, get(i, r), 1);
if (l != -1 && l + 1 < i)
add(l, i, get(l, i), 1);
}
else
{
int d = get(l, r);
int d1 = get(i, r);
int d2 = get(l, i);
if (d1 >= 0 || d2 >= 0)
{
add(i, r, d1, 1);
add(l, i, d2, 1);
assert(max(d1, d2) <= d);
add(l, r, max(d1, d2), -1);
}
}
}
Fl = vector<vector<pair<int, int>>>(N);
Fr = vector<vector<pair<int, int>>>(N);
for (const auto &dd : L)
{
int d = dd.first;
for (pair<int, int>lw : dd.second)
for (int i = lw.first; i < N; i |= i + 1)
{
if (!Fl[i].empty() && Fl[i].back().first == d)
Fl[i].back().second += lw.second;
else
Fl[i].push_back({d, lw.second});
}
}
for (const auto &dd : R)
{
int d = dd.first;
for (pair<int, int>rw : dd.second)
for (int i = rw.first; i < N; i |= i + 1)
{
if (!Fr[i].empty() && Fr[i].back().first == d)
Fr[i].back().second += rw.second;
else
Fr[i].push_back({d, rw.second});
}
}
for (int i = 0; i < N; i++)
{
for (int j = 1; j < (int)Fl[i].size(); j++)
Fl[i][j].second += Fl[i][j - 1].second;
for (int j = 1; j < (int)Fr[i].size(); j++)
Fr[i][j].second += Fr[i][j - 1].second;
}
}
int get(int l, int r, int d)
{
int ret = 0;
int i = r;
while (i >= 0)
{
if (!Fr[i].empty())
{
auto it = lower_bound(Fr[i].begin(), Fr[i].end(), make_pair(d, (int) - 1e9));
ret += Fr[i].back().second;
if (it != Fr[i].begin())
{
it--;
ret -= it->second;
}
}
i = (i & (i + 1)) - 1;
}
i = l - 1;
while (i >= 0) {
if (!Fl[i].empty())
{
auto it = lower_bound(Fl[i].begin(), Fl[i].end(), make_pair(d, (int) - 1e9));
ret -= Fl[i].back().second;
if (it != Fl[i].begin())
{
it--;
ret += it->second;
}
}
i = (i & (i + 1)) - 1;
}
return ret;
}
int max_towers(int L, int R, int D) {
int xx = -1;
int yy = -1;
{
int lo = L + 1;
int hi = N - 1;
while (lo < hi)
{
int m = (lo + hi) / 2;
if (medis.getmx(L, m).first - medis.getmn(L, m).first >= D)
hi = m;
else
lo = m + 1;
}
int m = lo;
pair<int, int>a = medis.getmx(L, m);
pair<int, int>b = medis.getmn(L, m);
if (a.first - b.first >= D)
{
if (a.second >= b.second)
xx = a.second;
else
xx = nxt[a.second];
}
}
{
int lo = 0;
int hi = R - 1;
while (lo < hi)
{
int m = (lo + hi + 1) / 2;
if (medis.getmx(m, R).first - medis.getmn(m, R).first >= D)
lo = m;
else
hi = m - 1;
}
int m = lo;
pair<int, int>a = medis.getmx(m, R);
pair<int, int>b = medis.getmn(m, R);
if (a.first - b.first >= D)
{
if (a.second <= b.second)
yy = a.second;
else
yy = prv[a.second];
}
}
if (xx != -1 && yy != -1 && xx <= yy)
return 2 + get(xx, yy, D);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1305 ms |
14724 KB |
Output is correct |
| 2 |
Correct |
2942 ms |
24528 KB |
Output is correct |
| 3 |
Correct |
2902 ms |
24488 KB |
Output is correct |
| 4 |
Correct |
2794 ms |
24472 KB |
Output is correct |
| 5 |
Correct |
3034 ms |
24460 KB |
Output is correct |
| 6 |
Correct |
2970 ms |
24488 KB |
Output is correct |
| 7 |
Correct |
2701 ms |
24500 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
720 KB |
Output is correct |
| 10 |
Correct |
1 ms |
720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
1st lines differ - on the 1st token, expected: '13', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
1st lines differ - on the 1st token, expected: '13', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3002 ms |
71680 KB |
4th lines differ - on the 1st token, expected: '13956', found: '13939' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
542 ms |
16872 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7196' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
1st lines differ - on the 1st token, expected: '13', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1305 ms |
14724 KB |
Output is correct |
| 2 |
Correct |
2942 ms |
24528 KB |
Output is correct |
| 3 |
Correct |
2902 ms |
24488 KB |
Output is correct |
| 4 |
Correct |
2794 ms |
24472 KB |
Output is correct |
| 5 |
Correct |
3034 ms |
24460 KB |
Output is correct |
| 6 |
Correct |
2970 ms |
24488 KB |
Output is correct |
| 7 |
Correct |
2701 ms |
24500 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
720 KB |
Output is correct |
| 10 |
Correct |
1 ms |
720 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
464 KB |
1st lines differ - on the 1st token, expected: '13', found: '2' |
| 12 |
Halted |
0 ms |
0 KB |
- |
