提出 #66335668

---

ソースコード 拡げる

/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308保佑我
//Missile保佑我
/*
* 醒了在梦里挣扎，不觉黯淡了朝霞
*/
/*
* 我很高兴你没有忘了我，但是我现在更希望你已经忘了我了。
* 希望在你的记忆中，我只是尘土一撮，从你的全世界路过，然后四散飞扬不留下一点痕迹，而你要不回头的往前走。
* 我更希望我只是从你的全世界路过，只是路过
*/
/*
* 只是我在十字路口守了太久，守到黄沙如雨掩埋一切痕迹，才发现自己等的人已经离开了。
*/
/*
* 听我的 别回头 回头就可能会泪流满面，会被黄沙掩埋，所以即使痛苦也要向前走
*/
/*
* 我听到了「天行健」的回响，这是一个伟大斗士的不息自强；
* 我听到了「破万法」的回响，这是一个黑道打手的守护欲望；
* 我看见了「生生不息」的激荡，这是一个骗子的伟大乐章！
*/
/*
* 我用虚假的面具照顾着细腻的感情；
* 我以华丽的衣物下藏着腐烂的血肉；
* 当我摘下面具，褪去衣物，即便是我最亲近的人，也无法直视我
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int n,D,R;
int a[MAXN],pos[MAXN],f[MAXN];
struct SGT {
	#define Ls(u) (u<<1)
	#define Rs(u) (u<<1|1)
	int sum[4*MAXN];
	void pushUp(int u)
	{
		sum[u]=max(sum[Ls(u)],sum[Rs(u)]);
	}
	void Build(int u,int l,int r)
	{
		if(l==r) {
			sum[u]=-1;
			return;
		}
		int mid=(l+r)>>1;
		Build(Ls(u),l,mid);
		Build(Rs(u),mid+1,r);
		pushUp(u);
	}
	void Modify(int u,int l,int r,int site,int val)
	{
		if(l==r) {
			sum[u]=max(sum[u],val);
			return;
		}
		int mid=(l+r)>>1;
		if(site<=mid) Modify(Ls(u),l,mid,site,val);
		else Modify(Rs(u),mid+1,r,site,val);
		pushUp(u);
	}
	int Query(int u,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R) return sum[u];
		int mid=(l+r)>>1,Ans=-1;
		if(L<=mid) Ans=max(Ans,Query(Ls(u),l,mid,L,R));
		if(mid+1<=R) Ans=max(Ans,Query(Rs(u),mid+1,r,L,R));
		return Ans;
	}
}tree;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>D>>R;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		pos[a[i]]=i;
	}
	int Ans=0;
	tree.Build(1,1,n);
	for(int i=1;i<=n;i++) {
		if(i-D>=1) tree.Modify(1,1,n,pos[i-D],f[i-D]);
		f[i]=tree.Query(1,1,n,max(1,pos[i]-R),min(n,pos[i]+R))+1;
		Ans=max(Ans,f[i]);
//		cout<<i<<" : "<<f[i]<<"\n";
	}
	cout<<Ans<<"\n";
	return 0;
}

提出情報

ジャッジ結果