#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> arr;
void init(int N, vector<int> H)
{
n = N, arr = H;
}
int max_towers(int L, int R, int D)
{
vector<int> l(n), r(n);
for (int i = 0; i < n; i++)
{
l[i] = i - 1, r[i] = i + 1;
while (l[i] >= 0 && arr[l[i]] - arr[i] < D) l[i]--;
while (r[i] < n && arr[r[i]] - arr[i] < D) r[i]++;
}
int st = L, en = R;
for (int i = L; i <= R; i++)
{
if (r[i] < r[st]) st = i;
}
for (int i = R; i >= L; i--)
{
if (l[i] > l[en]) en = i;
}
assert(st <= en);
if (st == en) return 1;
int res = 2, prv = st;
while (1)
{
int nxt = -1;
for (int i = prv + 1; i < en; i++)
{
if (!(l[i] > prv && r[i] < en)) continue;
if (nxt == -1) nxt = i;
else if (r[nxt] > r[i]) nxt = i;
}
if (nxt == -1) break;
res++;
prv = nxt;
}
return res;
}
# | 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... |