CF 187D BRT Contract

传送门

给了60分的nq暴力还是很资磁的！！！

基本上想的跟正解差不多了但是刚T2去了就没想细节QAQ

大概就是我们逆序求一下每一个点从0时刻开始走到终点需要用的时间f 我们需要找到它遇到的第一个红灯这个就是模意义下的一段区间最小值（把l[i]看做下标 i作为权值）这个可以通过动态开点线段树实现 or 离散化+权值线段树

对于每次询问一样的操作找到它遇到的第一个红灯然后 + f就可以了qwq

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 2002122500

#define ll long long

#define mxn 100100

using namespace std;

ll L[mxn],r,g,pre[mxn],lsh[mxn];

int mn[mxn*20],ls[mxn*20],rs[mxn*20];

int n,flag,poi;

ll f[mxn],t[mxn];

void pushup(int x){mn[x]=min(mn[ls[x]],mn[rs[x]]);}

void modify(int &x,ll l,ll r,ll d,int val)

{

	if(!x)	x=++poi;

	if(l==r){mn[x]=min(mn[x],val);return;}

	int mid=l+r>>1;

	if(d<=mid)	modify(ls[x],l,mid,d,val);

	else	modify(rs[x],mid+1,r,d,val);

	pushup(x);

}

ll query(int x,ll l,ll r,ll LL,ll RR)

{

	if(!x||RR<LL)	return inf;

	if(l>=LL&&r<=RR)	return mn[x];

	int mid=l+r>>1;ll ans=inf;

	if(LL<=mid)	ans=min(ans,query(ls[x],l,mid,LL,RR));

	if(RR>mid)	ans=min(ans,query(rs[x],mid+1,r,LL,RR));

	return ans;

}

int rt,q;ll p;

int main()

{

	scanf("%d%I64d%I64d",&n,&g,&r);

	memset(mn,48,sizeof(mn));p=g+r;

	for(int i=1;i<=n+1;i++)	scanf("%I64d",&L[i]),L[i]+=L[i-1];

	for(int i=n;i;i--)

	{

		ll _t=(p-L[i]%p)%p;

		ll mn=query(rt,0,p-1,max(0ll,g-_t),p-_t-1);

		if(g-_t<0)	mn=min(mn,query(rt,0,p-1,(p+g-_t),p-1));

		if(mn>n)	f[i]=L[n+1]-L[i];

		else	f[i]=L[mn]-L[i]+(p-(L[mn]-L[i])%p)+f[mn];

		modify(rt,0,p-1,L[i]%p,i);

	}

	scanf("%d",&q);

	while(q--)

	{

		ll _t,ans;scanf("%I64d",&_t);

		ll _=_t%p;

		ll mn=query(rt,0,p-1,max(0ll,g-_),p-_-1);

		if(g-_<0)	mn=min(mn,query(rt,0,p-1,(g-_+p),p-1));

		if(mn>n)	ans=L[n+1]+_t;

		else	ans=L[mn]+_t+(p-(L[mn]+_t)%p)+f[mn];

		printf("%I64d\n",ans);

	}

	return 0;

}

我现在怎么开始用_做变量名了越来越毒瘤了（

巴特西

CF 187D BRT Contract

传送门

最新文章

热门文章