#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>H;
struct ST
{
int l, r;
ST *left, *right;
int mn;
ST() {}
vector<pair<int, int>>V;
vector<pair<int, int>>W;
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);
}
else
{
left = right = NULL;
mn = H[l];
}
for (int i = l; i <= r; i++)
{
if (W.empty() || H[i] > W.back().first)
W.push_back({H[i], i});
}
int mm = 2e9;
for (int i = l + 1; i <= r; i++)
{
mm = min(mm, H[i - 1]);
if (V.empty() || H[i] - mm > V.back().first)
V.push_back({H[i] - mm, i});
}
}
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> get1(int L, int D, int mnl = 2e9)
{
if (L <= l)
{
int rr = -1;
auto it = lower_bound(V.begin(), V.end(), make_pair(D, -1));
if (it != V.end())
rr = it->second;
//W-mn>=D
//W>=D+mn
it = lower_bound(W.begin(), W.end(), make_pair(D + mnl, -1));
if (it != W.end())
{
int r1 = it->second;
if (rr == -1)
rr = r1;
else
rr = min(rr, r1);
}
return {rr, mn};
}
if (r < L)
return { -1, 2e9};
pair<int, int> i = left->get1(L, D, mnl);
pair<int, int> j = right->get1(L, D, min(i.second, mnl));
j.second = min(j.second, i.second);
if (i.first != -1)
j.first = i.first;
return j;
}
} 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 = medis.get1(L, D).first;
int yy = -1;
for (int y = R - 1; y >= L; y--)
{
if (medis.get(y + 1, R) + D <= H[y])
{
yy = y;
break;
}
}
if (xx != -1 && yy != -1 && xx <= yy)
return 2 + get(xx, yy, D);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4032 ms |
35584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
592 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1872 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
592 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1872 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1546 ms |
88444 KB |
Output is correct |
| 2 |
Correct |
1802 ms |
89100 KB |
Output is correct |
| 3 |
Correct |
1814 ms |
88840 KB |
Output is correct |
| 4 |
Correct |
1723 ms |
83980 KB |
Output is correct |
| 5 |
Correct |
1740 ms |
83512 KB |
Output is correct |
| 6 |
Correct |
1772 ms |
83780 KB |
Output is correct |
| 7 |
Correct |
1820 ms |
83836 KB |
Output is correct |
| 8 |
Execution timed out |
4096 ms |
67968 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
479 ms |
20924 KB |
3rd lines differ - on the 1st token, expected: '150', found: '151' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
592 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1872 KB |
1st lines differ - on the 1st token, expected: '292', found: '293' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4032 ms |
35584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
