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>
#include "towers.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
struct segtree{
vector<int>u,d;
void init(int n,vector<int>h){
u=h;
d.resize(4*n);
build(1,0,n-1);
}
void build(int v,int l,int r){
if(l==r){
d[v]=u[l];
return;
}
int mid=(l+r)>>1;
build(v*2,l,mid);
build(v*2,mid+1,r);
}
int query(int v,int l,int r,int L,int R){
if(R<L||r<L||R<l) return 0;
if(L<=l&&r<=R){
return d[v];
}
int mid=(l+r)>>1;
return max(query(v*2,l,mid,L,R),query(v*2+1,mid+1,r,L,R));
}
};
segtree sg;
int n;
vector<int>h;
vector<pair<int,int>>v;
vector<bool>used;
void init(int N,vector<int>H){
n=N; h=H;
used.resize(n);
for(int i=0;i<n;i++){
v.pb({H[i],i});
}
sort(all(v));
sg.init(n,h);
}
int max_towers(int L,int R,int D){
int ans=0;
set<int>st;
st.insert(-1);
st.insert(n);
for(auto [x,i]:v){
if(i<L||i>R) continue;
bool add=true;
auto it=st.lower_bound(i); it--; //*it is position
if(*it!=-1){
if(sg.query(1,0,n-1,(*it)+1,i-1)<x+D){
add=false;
}
}
it++;
if(*it!=n){
if(sg.query(1,0,n-1,i+1,(*it)-1)<x+D){
add=false;
}
}
if(add){
ans++;
st.insert(i);
}
}
return ans;
}
# | 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... |