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>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct ST{
vector<int> st;
void init(int x){
st.resize(4*x);
}
void update(int v,int L,int R,int p,int y){
if(L==R){
st[v]=max(st[v],y);
return;
}
int m=(L+R)/2;
if(p<=m){
update(2*v+1,L,m,p,y);
}
else{
update(2*v+2,m+1,R,p,y);
}
st[v]=max(st[2*v+1],st[2*v+2]);
}
int query(int v,int L,int R,int l,int r){
if(l==L && r==R){
return st[v];
}
int m=(L+R)/2;
if(r<=m){
return query(2*v+1,L,m,l,r);
}
else if(l>m){
return query(2*v+2,m+1,R,l,r);
}
else{
return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
}
}
}st;
bool cmp(pair<int,int> a,pair<int,int> b){
if(a.fs!=b.fs){
return a.fs<b.fs;
}
return a.sc>b.sc;
}
int main(){
AquA;
int n;
cin >> n;
int d;
cin >> d;
vector<int> v(n);
vector<pair<int,int> > g;
for(int i=0;i<n;i++){
cin >> v[i];
g.push_back({v[i],i});
}
vector<int> dp(n);
set<int> s1,s2;
s1.insert(-1);
sort(g.begin(),g.end(),cmp);
st.init(n);
int ans=0;
for(auto h:g){
auto y=s1.lower_bound(h.sc);
auto z=prev(y);
if(y!=s1.end()){
if((*y)-h.sc-1<d && ((*y)-(*z)-1>=d)){
s2.erase(*y);
}
}
if(h.sc-(*z)-1>=d){
s2.insert(h.sc);
}
s1.insert(h.sc);
auto u=s2.upper_bound(h.sc);
if(u==s2.begin()){
dp[h.sc]=st.query(0,0,n-1,0,h.sc)+1;
}
else{
dp[h.sc]=st.query(0,0,n-1,*(prev(u)),h.sc)+1;
}
st.update(0,0,n-1,h.sc,dp[h.sc]);
ans=max(ans,dp[h.sc]);
}
cout << ans << "\n";
return 0;
}
# | 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... |