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<bits/extc++.h>
using namespace std;
struct {
__gnu_pbds::gp_hash_table<int,int>mp;
int query(int pos){
int ans=0;
while(pos)
ans=max(ans,mp[pos]),
pos-=pos&-pos;
return ans;
}
void upd(long long pos,int x){
while(pos<=2e9)
mp[pos]=max(mp[pos],x),
pos+=pos&-pos;
}
void reset(){
mp.clear();
}
} BIT;
int goleft[200100], goright[200100], vl[200100];
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++){ cin>>vl[i];
goleft[i]=BIT.query(vl[i]-1)+1;
BIT.upd(vl[i],goleft[i]);
}
BIT.reset();
for(int i=n;i;i--){
goright[i]=BIT.query(1e9-vl[i])+1;
BIT.upd(1e9-vl[i]+1,goright[i]);
}
int ans=0;
BIT.reset();
for(int i=1;i<=n;i++){
ans=max(ans,goright[i]+BIT.query(vl[i]+x-1));
BIT.upd(vl[i],goleft[i]);
}
cout<<ans<<'\n';
}
# | 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... |