이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define vii vector<int>
#define vll vector<ll>
// 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively;
const int inf=INT_MAX;
struct segtree{
vector<int> t;
int sz;
void init(int n){
t.assign(4*n+5,0); sz=n;
}
void upd(int x, int l, int r, int ind, int val){
if(l==r){
t[x]=max(t[x],val); return;
}
int m=(l+r)/2;
if(ind<=m){
upd(x*2,l,m,ind,val);
}else upd(x*2+1,m+1,r,ind,val);
t[x]=max(t[x*2],t[x*2+1]);
return;
}
void upd(int ind, int val){
upd(1,1,sz,ind,val);
}
void erase(int x, int l, int r, int ind){
if(l==r){
t[x]=0;return;
}
int m=(l+r)/2;
if(ind<=m){
erase(x*2,l,m,ind);
}else erase(x*2+1,m+1,r,ind);
t[x]=max(t[x*2],t[x*2+1]);
return;
}
void erase(int ind){
erase(1,1,sz,ind);
}
int get(int x, int l, int r, int lx, int rx){
if(lx<=l&&r<=rx) return t[x];
if(lx>r||rx<l) return 0;
int m=(l+r)/2;
return max(get(x*2,l,m,lx,rx),get(x*2+1,m+1,r,lx,rx));
}
int get(int l, int r){
return get(1,1,sz,l,r);
}
};
void solve(){
int n,x; cin>>n>>x;
vector<int> a(n+1);
map<int,int> mp;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]=0;
int cnt=1;
for(auto &u:mp) u.S=cnt++;
vector<int> l(n+1),r(n+1);
segtree st;
st.init(n);
for(int i=1;i<=n;i++){
int ind=mp[a[i]];
l[i]=st.get(1,ind-1)+1;
st.upd(ind,l[i]);
}
st.init(n);
for(int i=n;i>0;i--){
int ind=mp[a[i]];
r[i]=st.get(ind+1,n)+1;
st.upd(ind,r[i]);
}
vector<pair<int,int>> v(n+1);
for(int i=1;i<=n;i++) v[i]={a[i],i};
sort(v.begin()+1,v.end());
vector<int> loc(n+1);
for(int i=1;i<=n;i++) loc[v[i].S]=i;
st.init(n);
for(int i=1;i<=n;i++) st.upd(loc[i],r[i]);
int ans=0;
for(int i=1;i<=n;i++){
st.erase(loc[i]);
int ind=upper_bound(v.begin()+1,v.end(),make_pair(a[i]-x,inf))-v.begin();
// cout<<ind<<"\n";
if(ind<=n){
ans=max(ans,l[i]+st.get(ind,n));
}
}
cout<<ans<<"\n";
}
int main(){
ios;
// int t; cin>>t; while(t--)
solve();
}
# | 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... |