codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
struct g{ int mi,ma; }; vector <g> tree; vector <int> a; g merger(g &l,g &r){ g ans; ans.mi=min(l.mi,r.mi); ans.ma=max(l.ma,r.ma); return ans; } void build(int node,int s,int e){ if(s==e){ tree[node]={a[s],a[e]}; return; } int m=(s+e)/2; build(node*2,s,m); build(node*2+1,m+1,e); tree[node]=merger(tree[node*2],tree[node*2+1]); } g query(int node,int s,int e,int l,int r){ if(s>e||s>r||e<l) return {INT_MAX,INT_MIN}; if(l<=s&&e<=r) return tree[node]; int m=(s+e)/2; g p1,p2; p1=query(node*2,s,m,l,r); p2=query(node*2+1,m+1,e,l,r); return merger(p1,p2); } int Solution::solve(vector<int> &v, int B) { int n=v.size(); vector < pair <int,int> > vp; for(int i=0;i<n;i++) vp.push_back({v[i],i}); sort(begin(vp),end(vp)); a.clear(); tree.clear(); tree.resize(4*n); vector <int> b; for(auto x:vp){ a.push_back(x.second); b.push_back(x.first); } build(1,0,n-1); int ans=1; for(int i=0;i<n;i++){ int l,r; l=upper_bound(begin(b),end(b),v[i]-B)-begin(b); r=upper_bound(begin(b),end(b),v[i])-begin(b); g q=query(1,0,n-1,l,r-1); if(q.mi!=INT_MAX) ans=max(ans,1+max(abs(i-q.ma),abs(i-q.mi))); } return ans; }
Private
[
?
]
Run code
Submit