#include "towers.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e5+7;
vector<int> a;
ll getlog[M];
ll n, Log;
ll d;
pair<ll,ll> sp[M][20];
pair<ll,ll> get(ll l , ll r)
{
ll dif = r-l+1;
ll my = getlog[dif];
return max(sp[l][my], sp[r-(1<<my)+1][my]);
}
void init(int N, std::vector<int> H) {
n = N; a = H;
for(int i = 0; i < n; i++) sp[i][0] = {a[i],i};
Log = log2(n)+1;
// cout << Log << endl;
for(int j = 1; j < Log; j++)
{
for(int i = 0; i < n; i++)
{
if(i+(1<<j)-1<n) sp[i][j] = max(sp[i][j-1],sp[i+(1<<j-1)][j-1]);
}
}
getlog[0] = -1;
for(int i = 1; i <= n; i++) getlog[i] = getlog[i/2]+1;
}
ll go(ll l, ll r, ll mxh)
{
if(r<l) return 0;
// cout << l << " " << r << " " << mxh << " " << get(l,r).second << endl;
ll biggest = get(l,r).second;
ll new_mxh = min(mxh,a[biggest]-d);
if(a[biggest]>mxh) return go(l,biggest-1,new_mxh) + go(biggest+1,r,new_mxh);
else return max(1LL,go(l,biggest-1,new_mxh) + go(biggest+1,r,new_mxh));
}
int max_towers(int L, int R, int D) {
d = D;
return go(L,R,1e18);
}
# | 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... |