Submission #66341994

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n,D,R,h[500010];
struct node{
	int l,r,mx;
}tr[500010*4];
void push_up(int p){
	tr[p].mx=max(tr[p*2].mx,tr[p*2+1].mx);
}
void build(int p,int l,int r){
	if(l==r){
		tr[p]=node({l,l,0});
		return ;
	}
	int mid=(l+r)/2;
	tr[p]=node({l,r,0});
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void upd(int p,int id,int val){
	if(tr[p].l==tr[p].r){
		tr[p].mx=val;
		return;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	if(id<=mid) upd(2*p,id,val);
	else upd(2*p+1,id,val);
	push_up(p);
}
int qr(int p,int L,int R){
	if(L<=tr[p].l&&tr[p].r<=R) return tr[p].mx;
	int mid=(tr[p].l+tr[p].r)/2;
	int res=0;
	if(L<=mid) res=max(res,qr(2*p,L,R));
	if(R>=mid+1) res=max(res,qr(2*p+1,L,R));
	return res;
}
int ans[500010],pos[500010];
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>D>>R;
	rep(i,1,n){
		cin>>h[i];
		pos[h[i]]=i;
	}
	build(1,1,n);
	int anss=0;
	rep(h,1,n){
		if(h-D>=1){
			upd(1,pos[h-D],ans[h-D]);
		}
		int l=max(1,pos[h]-R),r=min(pos[h]+R,n);
		ans[h]=qr(1,l,r)+1;
		anss=max(anss,ans[h]);
	}
	cout<<anss-1<<"\n";
	return 0;
}

Submission Info

Judge Result