#include "towers.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n;
int a[maxn], t[maxn * 4];
map < int, int > mp;
int pref[maxn];
void build(int i, int l, int r)
{
if(l == r)
{
t[i] = a[l];
return;
}
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
}
int ql, qr;
int query(int i, int l, int r)
{
if(qr < l || ql > r)return 0;
if(ql <= l && r <= qr)return t[i];
int mid = (l + r)/2;
return (query(2*i, l, mid), query(2*i+1, mid+1, r));
}
void init(int N, std::vector<int> H)
{
n = N;
for (int i = 0; i < n; ++ i)
{
a[i] = H[i];
mp[a[i]] = i;
}
for (int i = 0; i < n; ++ i)
{
if(i == 0)
{
pref[i] = 0;
if(a[i] < a[i+1])pref[i] ++;
}
else if(i == n-1)
{
pref[i] = pref[i-1];
if(a[i] < a[i-1])pref[i] ++;
}
else
{
pref[i] = pref[i-1];
if(a[i] < a[i+1] && a[i] < a[i-1])pref[i] ++;
}
}
}
int last[maxn], nxt[maxn];
int active[maxn];
/// shtoto ako imame po malko ot strani ne mojem da go vzemem zaedno s tekushtoto
/// a ako trqbva da izbirame iskame po malkoto
/// taka che vzimame po malkoto??
int max_towers(int L, int R, int D)
{
if(D == 1)
{
int sz = R - L + 1;
int ans = 0;
if(sz > 2)
{
ans += pref[R-1] - pref[L];
}
if(L < n-1 && a[L] < a[L+1])ans ++;
if(R > 0 && a[R] < a[R-1])ans ++;
return ans;
}
for (int i = L; i <= R; ++ i)
active[i] = 0;
vector < pair < int, int > > g;
for (int i = L; i <= R; ++ i)
{
g.pb(make_pair(a[i], i));
}
sort(g.begin(), g.end());
int cnt = 0;
for (auto &[val, i]: g)
{
/// cout << val << " " << i << endl;
int found = 0, no = 0;
for (int j = i-1; j >= L; -- j)
{
if(a[j] >= val + D)
{
found = 1;
break;
}
if(active[j])
{
no = 1;
break;
}
}
///cout << "found1 " << found << endl;
if(no)continue;
found = 0;
for (int j = i+1; j <= R; ++ j)
{
if(a[j] >= val + D)
{
found = 1;
break;
}
if(active[j])
{
no = 1;
break;
}
}
if(no)continue;
/// cout <<"found2 " << found << endl;
active[i] = 1;
cnt ++;
}
return cnt;
}
# | 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... |