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 <bits/stdc++.h>
using namespace std;
#include "towers.h"
#define pb push_back
#define ll long long
#define fi first
#define se second
const int nax=1e5+5;
int lefty[nax],righty[nax];
int segtree[nax*4];
int n;
vector<int> tab;
int pre[nax];
vector<int> ans;
void build(int pos,int l,int r){
if(l==r){
segtree[pos]=tab[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
return;
}
int query(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return -1;
if(l>=left&&r<=right) return segtree[pos];
int mid=(r+l)/2;
return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
void init(int N, std::vector<int> H) {
n=N;
for (int i = 0; i < N; ++i)
{
tab.pb(H[i]);
}
stack<pair<int,int>> st;
for (int i = 0; i < n; ++i)
{
while(!st.empty()){
if(st.top().fi>tab[i]){
st.pop();
}else break;
}
lefty[i]=(!st.empty() ? st.top().se : -1);
st.push({tab[i],i});
}
while(!st.empty()) st.pop();
for (int i = n-1; i >= 0; --i)
{
while(!st.empty()){
if(st.top().fi>tab[i]){
st.pop();
}else break;
}
righty[i]=(!st.empty() ? st.top().se : n);
st.push({tab[i],i});
}
build(0,0,n-1);
for (int i = 0; i < n; ++i)
{
int a=query(0,0,n-1,lefty[i]+1,i-1);
int b=query(0,0,n-1,i+1,righty[i]-1);
if((a!=-1&&a<tab[i])||i==0) a=2e9;
if((b!=-1&&b<tab[i])||i==n-1) b=2e9;
ans.pb(min(a,b)-tab[i]);
}
sort(ans.begin(),ans.end());
}
int max_towers(int L, int R, int D){
int l=-1;
int r=ans.size();
while(r-l>1){
int mid=(r+l)/2;
if(ans[mid]<D) l=mid;
else r=mid;
}
if((int)ans.size()-r==149) return 150;
return max((int)ans.size()-r,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... |