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 <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using mim = pair<pii,pii>;
const int maxn=1e5+10;
const int logg=18;
int n;
int h[maxn];
multiset<pii > res;
mim sparse[logg][maxn];
int klk;
int uniq[maxn];
pair<int,int> najs[2][logg][maxn];
mim comb(mim &a,mim &b){
mim ret=a;
ret.first=max(ret.first,b.first);
ret.second=min(ret.second,b.second);
return ret;
}
mim qry(int l,int r){
mim ret={{h[l],l},{h[l],l}};
for(int i=logg-1;i>=0;i--){
if(r-(1<<i)+1>=l){
ret=comb(ret,sparse[i][r]);
r-=(1<<i);
}
}
return ret;
}
void resi(int l,int r,multiset<pii > &ret,int naj=2e9+10){
if(r<l) return;
najs[0][0][l]=max(najs[0][0][l],{naj,l});
najs[1][0][r]=max(najs[1][0][r],{naj,r});
auto temp=qry(l,r);
pii maxi=temp.first;
pii mini=temp.second;
multiset<pii> levi; multiset<pii> desni;
resi(l,maxi.second-1,levi,maxi.first);
resi(maxi.second+1,r,desni,maxi.first);
if(levi.size()>desni.size()) swap(levi,desni);
for(auto i:desni) levi.emplace(i);
if(!levi.empty()){
auto najv=--levi.end();
int d=naj-mini.first;
if((*najv).first<d){
levi.erase(najv);
levi.emplace(pii(d,mini.second));
}
}else{
levi.emplace(pii(naj-mini.first,mini.second));
}
swap(ret,levi);
}
void init(int _n, vector<int> _h) {
n=_n;
for(int i=0;i<n;i++) najs[0][0][i]=najs[1][0][i]={-1,-1};
for(int i=0;i<n;i++) h[i]=_h[i];
for(int i=0;i<logg;i++){
for(int j=0;j<n;j++){
if(i==0) sparse[i][j]={{h[j],j},{h[j],j}};
else if(j-(1<<(i-1))>=0) sparse[i][j]=comb(sparse[i-1][j],sparse[i-1][j-(1<<(i-1))]);
else sparse[i][j]=sparse[i-1][j];
}
}
resi(0,n-1,res);
for(int i=1;i<logg;i++){
for(int j=0;j<n;j++){
if(j-(1<<(i-1))) najs[0][i][j]=max(najs[0][i][j],najs[0][i-1][j-(1<<(i-1))]);
else najs[0][i][j]=najs[0][i-1][j];
if(j-(1<<(i-1))) najs[1][i][j]=max(najs[1][i][j],najs[1][i-1][j-(1<<(i-1))]);
else najs[1][i][j]=najs[1][i-1][j];
}
}
}
pii najupit(int l,int r,int koji){
pii ret={-1,-1};
for(int i=logg-1;i>=0;i--){
if(r-(1<<i)+1>=l){
ret=max(ret,najs[koji][i][r]);
r-=(1<<i);
}
}
return ret;
}
int D=-1;
pair<int,pii> segt[4*maxn+10];
pair<int,pii> combseg(const pair<int,pii> a,const pair<int,pii> b){
pair<int,pii> ret;
ret.first=a.first+b.first;
ret.second.first=max(a.second.first,b.second.first);
ret.second.second=min(a.second.second,b.second.second);
return ret;
}
void update(int t,int v,int ind=1,int l=0,int r=n-1){
if(l==r){
segt[ind]={1,{v,v}};
return;
}
int mid=l+(r-l)/2;
if(t<=mid) update(t,v,2*ind,l,mid);
else update(t,v,2*ind+1,mid+1,r);
segt[ind]=combseg(segt[2*ind],segt[2*ind+1]);
}
pair<int,pii> query(int tl,int tr,int ind=1,int l=0,int r=n-1){
if(tl<=l && r<=tr) return segt[ind];
int mid=l+(r-l)/2;
if(tr<=mid) return query(tl,tr,2*ind,l,mid);
if(tl>mid) return query(tl,tr,2*ind+1,mid+1,r);
return combseg(query(tl,tr,2*ind,l,mid),query(tl,tr,2*ind+1,mid+1,r));
}
int max_towers(int l, int r, int d) {
if(D==-1){
for(int i=0;i<4*maxn+10;i++) segt[i]={0,{-1,INT_MAX}};
for(auto i:res){
if(i.first>=d) update(i.second,i.second);
}
D=d;
}
if(l==r) return 1;
auto temp=query(l,r);
int ret=temp.first;
int prvi=temp.second.second;
int posl=temp.second.first;
if(prvi==INT_MAX){
prvi=r+1;
posl=l-1;
}
if(l+1<=r-1) ret=query(l+1,r-1).first;
else ret=0;
if(h[l]<h[l+1]) ret++;
if(h[r]<h[r-1]) ret++;
return ret;
// za levo
if(prvi-1>=l){
auto tmp=najupit(l,prvi-1,1);
int koji=tmp.second;
int naj=tmp.first;
if(qry(l,koji).second.first<=naj-d) ret++;
}
// za desno
if(posl+1<=r){
auto tmp=najupit(posl+1,r,0);
int koji=tmp.second;
int naj=tmp.first;
if(qry(koji,r).second.first<=naj-d) ret++;
}
return ret;
}
# | 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... |