WA 求助
查看原帖
WA 求助
556362
Unnamed114514楼主2022/7/26 08:33
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int maxn=1e5+5;
int dp1[maxn][20],dp2[maxn][20],n,s,L,dp[maxn],cnt;
int ask(int l,int r){
	int k=log2(r-l+1);
	return max(dp1[l][k],dp1[r-(1<<k)+1][k])-min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
inline int read(){
	int res=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		f|=(ch=='-');
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return f?-res:res;
}
int t[maxn<<2];
void add(int k,int l,int r,int x,int v){
	if(l==r){
		t[k]=v;
		return;
	}
	int mid=l+r>>1;
	if(mid>=x)
		add(ls,l,mid,x,v);
	else
		add(rs,mid+1,r,x,v);
	t[k]=min(t[ls],t[rs]);
}
int query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)
		return t[k];
	int mid=l+r>>1,res=inf;
	if(mid>=x)
		res=min(res,query(ls,l,mid,x,y));
	if(mid<y)
		res=min(res,query(rs,mid+1,r,x,y));
	return res;
}
int main(){
	n=read(),s=read(),L=read();
	for(int i=1;i<=n;i++)
		dp1[i][0]=dp2[i][0]=read();
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++){
			dp1[j][i]=max(dp1[j][i-1],dp1[j+(1<<(i-1))][i-1]);
			dp2[j][i]=min(dp2[j][i-1],dp2[j+(1<<(i-1))][i-1]);
		}
	memset(t,inf,sizeof(t));
	memset(dp,inf,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
		add(1,1,n,i,dp[i-1]);
		if(i<L){
			dp[i]=0;
			continue;
		}
		if(ask(i-L+1,i)>s){
			dp[i]=inf;
			continue;
		}
		int l=1,r=i-L+1;
		while(l<r){
			int mid=l+r>>1;
			if(ask(mid,i)<=s)
				r=mid;
			else
				l=mid+1;
		}
		dp[i]=query(1,1,n,r,i-L+1)+1;
	}
	if(dp[n]>=inf)
		puts("-1");
	else
		printf("%d\n",dp[n]);
	return 0;
}
2022/7/26 08:33
加载中...