开始 2023-12-19 22:53:18

【2024省选前】20231219更正

结束 2023-12-31 00:00:00
Contest is over.
当前 2025-02-23 07:06:36

T1
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int n,g,r;
int d[50010],ordo[50010];
long long s[50010],f[50010];
int w[133333];
#define T 65536
int gmin(int a,int b){return a<b?a:b;}
int Q(int l,int r){int res=n;for(l+=T-1,r+=T+1;l^r^1;l>>=1,r>>=1)l&1?:res=gmin(res,w[l^1]),~r&1?:res=gmin(res,w[r^1]);return res;}
void C(int t,int x){for(w[t+=T]=x;t>>=1;)w[t]=gmin(w[t<<1],w[t<<1|1]);}
struct cross
{
	long long s;
	int i;
	inline bool operator<(const cross B)const{return s<B.s;}
}a[50010];
int main()
{
	int i,j,q,l,r,t;
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	long long Ha;
	!scanf("%d%d%d",&n,&g,&r);n++;
	Ha=g+r;
	for(i=1;i<=n;i++)
	{
		!scanf("%d",&d[i]);
		a[i].i=i;
		a[i].s=(a[i-1].s+d[i])%Ha;
		s[i]=s[i-1]+d[i];
	}
	sort(&a[1],&a[n+1]);
	for(i=1;i<=n;i++)ordo[a[i].i]=i;
	memset(w,63,sizeof(w));
	f[n]=0;
	for(i=n-1;i;i--)
	{
		l=lower_bound(&a[1],&a[n+1],(cross){(g+s[i])%Ha,0})-a;
		r=lower_bound(&a[1],&a[n+1],(cross){s[i]%Ha,0})-a-1;
		//printf("%d %d\n",l,r);
		if(l==r+1)
		{
			if(d[i+1]%Ha>=g)j=i+1;
			else j=n;
		}
		else if(l>r)j=gmin(Q(1,r),Q(l,n));
		else j=Q(l,r);
		if(j==n)f[i]=s[j]-s[i];
		else f[i]=f[j]+(s[j]-s[i]+Ha-1)/Ha*Ha;
		//printf("%d %d\n",j,f[i]);
		C(ordo[i],i);
	}
	for(!scanf("%d",&q);q--;)
	{
		!scanf("%d",&t);
		l=lower_bound(&a[1],&a[n+1],(cross){((g-t)%Ha+Ha)%Ha,0})-a;
		r=lower_bound(&a[1],&a[n+1],(cross){((-t)%Ha+Ha)%Ha,0})-a-1;
		//printf("%d %d\n",l,r);
		if(l==r+1)
		{
			if((d[1]+t)%Ha>=g)j=i+1;
			else j=n;
		}
		else if(l>r)j=gmin(Q(1,r),Q(l,n));
		else j=Q(l,r);
		//printf("%d\n",j);
		printf("%lld\n",j==n?s[n]+t:(s[j]+t+Ha-1)/Ha*Ha+f[j]);
	}
	return 0;
}

admin  •  1年前

比赛已结束。