记录编号	575897	评测结果	AAAAAAAAAA
题目名称	简短的题目	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	1.046 s
提交时间	2022-09-30 10:19:01	内存使用	20.61 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res,res1;
ll pr[100010],sf[100010],tree[400010],tree1[400010],tr[400010],laz[400010];
int n,L,R,p,p1;
int a[100010],pos[400010],pos1[400010];
void build(int id,int l,int r){
	laz[id]=tr[id]=-2e18;
	if(l==r){
		tree[id]=tree1[id]=pr[l];
		pos[id]=pos1[id]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	if(tree[id<<1]>tree[id<<1|1]){
		tree[id]=tree[id<<1];
		pos[id]=pos[id<<1];
	}
	else{
		tree[id]=tree[id<<1|1];
		pos[id]=pos[id<<1|1];
	}
	if(tree1[id<<1]<tree1[id<<1|1]){
		tree1[id]=tree1[id<<1];
		pos1[id]=pos1[id<<1];
	}
	else{
		tree1[id]=tree1[id<<1|1];
		pos1[id]=pos1[id<<1|1];
	}
}
void query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		if(tree[id]>res){
			res=tree[id];
			p=pos[id];
		}
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) query(id<<1,l,mid,ql,qr);
	if(qr>mid) query(id<<1|1,mid+1,r,ql,qr);
}
void query1(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		if(tree1[id]<res1){
			res1=tree1[id];
			p1=pos1[id];
		}
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) query1(id<<1,l,mid,ql,qr);
	if(qr>mid) query1(id<<1|1,mid+1,r,ql,qr);
}
void pushdown(int id){
	if(laz[id]!=-2e18){
		tr[id<<1]=max(tr[id<<1],laz[id]);
		tr[id<<1|1]=max(tr[id<<1|1],laz[id]);
		laz[id<<1]=max(laz[id<<1],laz[id]);
		laz[id<<1|1]=max(laz[id<<1|1],laz[id]);
		laz[id]=-2e18;
	}
}
void update(int id,int l,int r,int ul,int ur,ll x){
	if(ul<=l&&r<=ur){
		tr[id]=max(tr[id],x);
		laz[id]=max(laz[id],x);
		return;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	if(ul<=mid) update(id<<1,l,mid,ul,ur,x);
	if(ur>mid) update(id<<1|1,mid+1,r,ul,ur,x);
}
void solve(int id,int l,int r){
	if(l==r){
		printf("%lld ",tr[id]);
		return;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	solve(id<<1,l,mid);
	solve(id<<1|1,mid+1,r);
}
bool flag1,flag2,flag3;
int main(){
	freopen("wwydatsv.in","r",stdin);
	freopen("wwydatsv.out","w",stdout);
	flag1=flag2=flag3=1;
	scanf("%d%d%d",&n,&L,&R);
	if(n>10&&R-L+1>10) flag3=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(i>1&&a[i]!=a[i-1]) flag1=0;
		if(a[i]<0) flag2=0;
		pr[i]=pr[i-1]+a[i];
	}
	build(1,1,n);
	if(flag3==1){
		for(int i=1;i+L-1<=n;i++)
		for(int j=i+L-1;j<=min(i+R-1,n);j++)
		update(1,1,n,i,j,pr[j]-pr[i-1]);
		solve(1,1,n);
		return 0;
	}
	if(flag2==1){
		for(int i=1;i+R-1<=n;i++)
		update(1,1,n,i,i+R-1,pr[i+R-1]-pr[i-1]);
		solve(1,1,n);
		return 0;
	}
	if(flag1==1){
		ll ans=a[1]<0?a[1]*1ll*L:a[1]*1ll*R;
		for(int i=1;i<=n;i++)
		printf("%lld ",ans);
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(i+L-1<=min(i+R-1,n)){
			res=-2e18,p=0;
			query(1,1,n,i+L-1,min(i+R-1,n));
			int len=p-i+1;
			update(1,1,n,i,p,pr[p]-pr[i-1]);
			if(len<R&&i>1){
				res1=2e18,p1=0;
				if(max(i-(R-len)-1,1)<=i-1){
					query1(1,1,n,max(i-(R-len)-1,1),i-1);
					update(1,1,n,p1+1,p,pr[p]-pr[p1]);
				}
				if(i-(R-len)-1<1) update(1,1,n,1,p,pr[p]);
			}
		}
		if(max(i-R,1)<=i-L){
			res1=2e18,p1=0;
			query1(1,1,n,max(i-R,1),i-L);
			int len=i-p1;
			update(1,1,n,p1+1,i,pr[i]-pr[p1]);
			if(len<R&&i<n){
				res=-2e18,p=0;
				if(i+1<=min(i+(R-len),n)){
					query(1,1,n,i+1,min(i+(R-len),n));
					update(1,1,n,p1+1,p,pr[p]-pr[p1]);
				}
			}
		}
	}
	solve(1,1,n);
}