This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
using ii = pair<int, int>;
int N;
vector<int> H;
void init(int N, vector<int> H) {
::N = N;
::H = H;
}
int max_towers(int L, int R, int D) {
vector<int> V(H.begin() + L, H.begin() + R + 1), cl(V.size(), -1), cr(V.size(), V.size());
vector<ii> vec;
for (int i = 0; i < (int)V.size(); i++) {
{
int lo = 0, hi = (int)vec.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (vec[mid].first - D >= V[i]) {
cl[i] = vec[mid].second;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
while (!vec.empty() && vec.back().first <= V[i]) {
vec.pop_back();
}
vec.eb(V[i], i);
}
vec.clear();
for (int i = (int)V.size() - 1; i >= 0; i--) {
{
int lo = 0, hi = (int)vec.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (vec[mid].first - D >= V[i]) {
cr[i] = vec[mid].second;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
while (!vec.empty() && vec.back().first <= V[i]) {
vec.pop_back();
}
vec.eb(V[i], i);
}
//~ for (int i : V) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
//~ for (int i : cl) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
//~ for (int i : cr) {
//~ cout << i << ' ';
//~ }
//~ cout << '\n';
function<int(int, int, bool, bool)> solve = [&](int l, int r, bool a = 0, bool b = 0) {
if (l > r) {
return 0;
}
ii to = mp((int)2e9, -1);
for (int i = l; i <= r; i++) {
if ((!a || l <= cl[i]) && (!b || cr[i] <= r)) {
to = min(to, mp(V[i], i));
}
}
if (to.second != -1) {
return solve(l, to.second - 1, a, 1) + solve(to.second + 1, r, 1, b) + 1;
} else {
return 0;
}
};
return solve(0, (int)V.size() - 1, 0, 0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |