#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct ST
{
int l, r;
ST *left, *right;
int mn;
ST() {}
ST(int l, int r, const vector<int>& h): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2, h);
right = new ST((l + r) / 2 + 1, r, h);
mn = min(left->mn, right->mn);
}
else
{
left = right = NULL;
mn = h[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));
}
} medis;
vector<vector<pair<int, int>>>Fl, Fr;
int N;
vector<int>H;
void init(int N_, vector<int> H_) {
N = N_;
H = H_;
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, H);
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;
for (int x = L + 1; x <= R; x++)
{
if (medis.get(L, x - 1) + D <= H[x])
{
xx = x;
break;
}
}
for (int y = R; 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 |
4043 ms |
12360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1488 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 |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1488 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 |
1395 ms |
67880 KB |
Output is correct |
| 2 |
Correct |
1738 ms |
68296 KB |
Output is correct |
| 3 |
Correct |
1729 ms |
68332 KB |
Output is correct |
| 4 |
Correct |
1692 ms |
63268 KB |
Output is correct |
| 5 |
Correct |
1659 ms |
62776 KB |
Output is correct |
| 6 |
Correct |
1640 ms |
63288 KB |
Output is correct |
| 7 |
Correct |
1541 ms |
63392 KB |
Output is correct |
| 8 |
Execution timed out |
4018 ms |
20552 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
410 ms |
16064 KB |
43rd lines differ - on the 1st token, expected: '1278', found: '1279' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1488 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 |
4043 ms |
12360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
