# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1267378 | Faggi | Radio Towers (IOI22_towers) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
vector<int>h;
vector<ll>v;
void init(int N, std::vector<int> H) {
h=H;
v.resize(N,0);
n=N;
ll i;
for(i=1; i<N; i++)
{
v[i]=v[i-1];
if(i+1<N&&H[i]<H[i+1]&&H[i]<H[i-1])
v[i]++;
}
}
bool in=0;
void ini(ll D)
{
in=1;
ll i;
for(i=1; i<N; i++)
{
v[i]=v[i-1];
if(i+1<N&&H[i]<=H[i+1]-D&&H[i]<=H[i-1]-D)
v[i]++;
}
}
int max_towers(int L, int R, int D) {
if(in==0)
ini(D);
if(L==R)
return 1;
int ans=v[R-1]-v[L];
if(h[L]<=h[L+1]-D)
ans++;
if(h[R]<=h[R-1]-D)
ans++;
return ans;
}