#include "towers.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
const ll big = 1e9+10;
ll n;
vector<ll> h;
//ll mx;
vector<ll> ps;
vector<pair<ll,ll>> rgs;
struct obj{
ll v,c;
bool operator<(const obj &o) const{
return v<o.v;
}
bool operator>(const obj &o) const{
return v>o.v;
}
};
void init(int N, std::vector<int> H) {
n = N;
h = H;
//for(ll i = 0;i<n;i++) if((i==0||(h[i-1]<h[i]))&&(i==n-1||h[i]>h[i+1])) mx = i;
//for(ll i = 1;i<n-1;i++){
// if (h[i-1]<h[i]&&h[i]>h[i+1]){
// ps.push_back(i);
// }
//}
//for(auto [u,v] : ps) cerr << "[" << u << "," << v << "]" << " ";cerr << "\n";
}
bool ps_inited = false;
void init_ps(ll d){
ps_inited = true;
vector<ll> l(n,0),r(n,0);
vector<ll> ld(n,big),rd(n,big);
{
vector<pair<ll,ll>> v;
v.push_back({h[0],0});
for(ll i = 1;i<n;i++){
auto it = lower_bound(v.begin(),v.end(),make_pair(h[i]-d+1,0));
if (it!=v.begin()) ld[i] = i-(*--it).second;
while(v.size()&&v.back().first>h[i]) v.pop_back();
v.push_back({h[i],i});
}
}
{
vector<pair<ll,ll>> v;
v.push_back({h[n-1],n-1});
for(ll i = n-2;i>=0;i--){
auto it = lower_bound(v.begin(),v.end(),make_pair(h[i]-d+1,0));
if (it!=v.begin()) rd[i] = (*--it).second-i;
while(v.size()&&v.back().first>h[i]) v.pop_back();
v.push_back({h[i],i});
}
}
{
vector<pair<ll,ll>> v;
v.push_back({h[0],h[0]});
for(ll i = 1;i<n;i++){
ll mi = h[i];
while(v.size()&&v.back().first<h[i]){
mi = min(mi,v.back().second);
v.pop_back();
}
if (mi<=h[i]-d) l[i] = 1;
v.push_back({h[i],mi});
}
}
{
vector<pair<ll,ll>> v;
v.push_back({h[n-1],h[n-1]});
for(ll i = n-2;i>=0;i--){
ll mi = h[i];
while(v.size()&&v.back().first<h[i]){
mi = min(mi,v.back().second);
v.pop_back();
}
if (mi<=h[i]-d) r[i] = 1;
v.push_back({h[i],mi});
}
}
for(ll i = 0;i<n;i++) if(l[i]&&r[i]) {
ps.push_back(i);
rgs.push_back({i-max(1,ld[i]),i+max(1,rd[i])});
//cerr << i-ld[i] << " " << i << " " << i+rd[i] << "\n";
}
}
int max_towers(int L, int R, int D) {
if(!ps_inited) init_ps(D);
ll l = L, r = R, d = D;
ll ans = 1;
//auto it0 = lower_bound(ps.begin(),ps.end(),r);
//ll rf = it0-ps.begin();
//auto it1 = lower_bound(ps.begin(),ps.end(),l+1);
//ll lf = it1-ps.begin();
//cerr << lf << " " << rf << "\n";
//ans = max(0,rf-lf)+1;
auto it0 = lower_bound(rgs.begin(),rgs.end(),make_pair(r,0));
//if (it0!=rgs.begin()) --it0;
ll rf = it0-rgs.begin();
auto it1 = lower_bound(rgs.begin(),rgs.end(),make_pair(l,0));
ll lf = it1-rgs.begin();
ans = max(0,rf-lf)+1;
return ans;
/*vector<obj> a,b;
a.push_back({0,0});
b.push_back({big,0});
for(ll i = l;i<=r;i++){
ll cur = 0;
auto it = lower_bound(b.begin(),b.end(),obj({h[i]-1,0}),greater<obj>());
--it;
cur = (*it).c;
ans = max(ans,cur+1);
obj oa = {h[i],cur+1};
if (a.size()<=oa.c) a.push_back(oa);
else a[oa.c] = min(a[oa.c],oa);
auto it0 = lower_bound(a.begin(),a.end(),obj({h[i]-d+1,0}));
--it0;
obj ob = {h[i]-d,(*it0).c};
if (b.size()<=ob.c) b.push_back(ob);
else b[ob.c] = max(b[ob.c],ob);
ans = max(ans,cur+1);
//cerr << "a:";for(auto [u,v] : a) cerr << "(" << u <<"," << v << ") ";cerr << "\n";
//cerr << "b:";for(auto [u,v] : b) cerr << "(" << u <<"," << v << ") ";cerr << "\n";
}*/
return ans;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:94:20: warning: unused variable 'd' [-Wunused-variable]
94 | ll l = L, r = R, d = D;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
2620 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
466 ms |
3540 KB |
8th lines differ - on the 1st token, expected: '9', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
1112 KB |
2nd lines differ - on the 1st token, expected: '7063', found: '7197' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
2620 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
