This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towers.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
const ll big = 1e9+10;
ll n;
ll w;
vector<ll> h,lh,rh,hh,hs,inc,decc;
//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;
}
};
struct dat{
ll c,l,r;
dat():c(0),l(big),r(-big){}
dat(ll x, ll y, ll z):c(x),l(y),r(z){}
void put(ll i){
c = 1;
l = i;
r = i;
}
dat operator+(const dat &o) const{
return dat(c+o.c,min(l,o.l),max(r,o.r));
}
};
struct node{
ll l,r,m;
dat v;
node *L,*R;
node(ll a, ll b):l(a),r(b),m(a+b>>1),v(),L(nullptr),R(nullptr){
if(a<b){
L = new node(l,m);
R = new node(m+1,r);
}
}
void put(ll i){
if (l==r) v.put(i);
else{
if (i<=m) (L=new node(*L))->put(i);
else (R=new node(*R))->put(i);
v = L->v+R->v;
}
}
dat qry(ll ql, ll qr){
//cerr << "qry " << ql << " " << qr << " " << l << " " << r << " " << v.l << " " << v.r << " " << v.c << "\n";
if (ql<=l&&r<=qr) return v;
else{
if (qr<=m) return L->qry(ql,qr);
else if (ql>m) return R->qry(ql,qr);
else return L->qry(ql,qr)+R->qry(ql,qr);
}
}
};
struct segtree{
vector<node*> rt;
segtree(){}
segtree(ll n){
rt.push_back(new node(0,n-1));
}
void nw(){
rt.push_back(new node(*rt.back()));
}
void put(ll t, ll i){
rt[t]->put(i);
}
dat qry(ll t, ll ql, ll qr){
return rt[t]->qry(ql,qr);
}
};
segtree t;
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";
lh.resize(n,0);
rh.resize(n,0);
hh.resize(n,0);
{
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();
}
lh[i] = h[i]-mi;
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();
}
rh[i] = h[i]-mi;
v.push_back({h[i],mi});
}
}
for(ll i = 0;i<n;i++) hh[i] = min(lh[i],rh[i]);
hs = hh;
sort(hs.begin(),hs.end());
hs.erase(unique(hs.begin(),hs.end()),hs.end());
t = segtree(n);
w = hs.size();
vector<vector<ll>> adds(w);
for(ll i = 0;i<n;i++){
ll p = lower_bound(hs.begin(),hs.end(),hh[i])-hs.begin();
adds[p].push_back(i);
}
for(ll i = w-1;i>=0;i--){
t.nw();
for(ll j : adds[i]){
t.put(w-i,j);
//cerr << "add " << hs[i] << " " << j << "\n";
}
dat o = t.qry(w-i,0,n-1);
//cerr << hs[i] << " " << o.l << " " << o.r << " " << o.c << "\n";
}
inc = decc = h;
for(ll i = 1;i<n;i++) decc[i] = min(decc[i],decc[i-1]);
for(ll i = n-2;i>=0;i--) inc[i] = min(inc[i],inc[i+1]);
}
bool ps_inited = false;
void init_ps(ll d){
ps_inited = true;
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});
}
}
for(ll i = 0;i<n;i++) if(lh[i]>=d&&rh[i]>=d) {
ps.push_back(i);
rgs.push_back({i-ld[i],i+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;
ll idx = w-(lower_bound(hs.begin(),hs.end(),d)-hs.begin());
dat o = t.qry(idx,L,R);
//cerr << idx << " " << L << " " << R << " " << o.l << " " << o.r << " " << o.c << "\n";
if (o.c==0) return 1;
ll cur = o.c;
ll l_need = upper_bound(inc.begin(),inc.end(),h[o.l]-d)-inc.begin();
if (l_need-1<L) cur--;
ll r_need = lower_bound(decc.begin(),decc.end(),h[o.r]-d,greater<ll>())-decc.begin();
if (r_need>R) cur--;
return 1+max(0,cur);
//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();
if (it0!=rgs.begin()){
if ((*--it0).second>r) --rf;
}
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 (stderr)
towers.cpp: In constructor 'node::node(ll, ll)':
towers.cpp:40:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | node(ll a, ll b):l(a),r(b),m(a+b>>1),v(),L(nullptr),R(nullptr){
| ~^~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:138:9: warning: variable 'o' set but not used [-Wunused-but-set-variable]
138 | dat o = t.qry(w-i,0,n-1);
| ^
# | 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... |