记录编号	244315	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]工作评估	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	7.358 s
提交时间	2016-03-31 18:29:46	内存使用	117.86 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100000+10;
const int size=150;
const int oo=2000000000;
struct node
{
	int first,second;
} block[maxn/size+5][size*size+5],start[maxn/size+5][size+5],end[maxn/size+5][size+5];
int bn[maxn/size+5],sn[maxn/size+5],en[maxn/size+5];
int blockl[maxn/size+5],blockd[maxn/size+5];
int limit[maxn],delta[maxn];
int n,m;

bool cmq(const node &a,const node &b)
{
	return (a.first<b.first || (a.first==b.first && a.second<b.second));
}

void process(node p[],int &n)
{
	sort(p,p+n,cmq);
	int _n=n;n=0;
	for (int i=1;i<_n;i++)
	{
		while (n>=0 && p[i].second>=p[n].second) n--;
		p[++n]=p[i];
	}
	n++;
}	

void prepare()
{
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) scanf("%d",&delta[i]);
	for (int i=0;i<n;i++) scanf("%d",&limit[i]);
	for (int i=0;i*size<n;i++)
	{
		int l=i*size,r=i*size+size-1;
		if (r>=n) r=n-1;
		for (int u=l;u<=r;u++)
		for (int v=u,pl=oo,pd=0;v>=l;v--)
		{
			int nd=pd+delta[v],nl=min(pl,limit[v]+pd);
			node xxx;xxx.first=nl;xxx.second=nd;
			if (nd>pd) block[i][bn[i]++]=xxx;
			if (v==l) start[i][sn[i]++]=xxx;
			if (u==r) end[i][en[i]++]=xxx;
			if (v==l && u==r) blockl[i]=nl,blockd[i]=nd;
			pl=nl;pd=nd;
		}
		process(block[i],bn[i]);
		process(start[i],sn[i]);
		process(end[i],en[i]);
	}

	//printf("%0.9lf\n",(double)clock()/CLOCKS_PER_SEC);
}

int getbest(node p[],int n,int v,int nowbest)
{
	if (nowbest>=v+p[0].second) return nowbest;
	int l=-1,r=n;
	while (l+1<r)
	{
		int mid=((l+r)>>1);
		if (v+p[mid].second>=p[mid].first) l=mid;
		else r=mid;
	}
	int res=v;
	if (l>=0 && l<n) res=max(res,p[l].first);
	if (l+1<n) res=max(res,p[l+1].second+v);
	return res;
}

void work()
{
	for (;m--;)
	{
		int L,R,V,now,res;
		scanf("%d%d%d",&L,&R,&V);res=now=V;
		L--;R--;
		int xxx=0;
		for (int i=L/size;i<=R/size;i++)
		if (i*size>=L && i*size+size-1<=R)
		{
			res=max(res,getbest(block[i],bn[i],V,res));
			res=max(res,getbest(start[i],sn[i],now,res));
			now=max(min(blockl[i],now+blockd[i]),getbest(end[i],en[i],V,-oo));
		} else
		{
			for (int j=max(L,i*size),tmp=now;j<=R && j<i*size+size;j++)
			{
				tmp=max(V,min(tmp+delta[j],limit[j]));
				res=max(res,tmp);
			}
			if (R>i*size+size-1)
			for (int j=min(R,i*size+size-1),pl=oo,pd=0;j>=L && j>=i*size;j--)
			{
				int nd=pd+delta[j],nl=min(pl,limit[j]+pd);
				now=max(now,min(V+nd,nl));
				pl=nl;pd=nd;
			}	
		}
		printf("%d\n",res);
	}
	//printf("%0.9lf\n",(double)clock()/CLOCKS_PER_SEC);
}

int main()   
{
	freopen("nt2011_zej_b.in","r",stdin);
	freopen("nt2011_zej_b.out","w",stdout);
	prepare();
	work();
}