Submission #1867923

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300010
#define LL long long
using namespace std;

int n,m;
LL a[MAXN],s1[MAXN],s2[MAXN];
int pre[MAXN];
LL f1[MAXN],f2[MAXN];
LL ans[MAXN],temp[MAXN];

namespace Convex{
	LL xp[MAXN],yp[MAXN];
	int q[MAXN],head,tail;

	void init(){
		head=0;
		tail=-1;
	}

	void addPoint(int id,LL x,LL y){
		xp[id]=x;
		yp[id]=y;
		while(head<tail && (yp[q[tail]]-yp[q[tail-1]])*(xp[id]-xp[q[tail]]) 
													<=
						   (yp[id]-yp[q[tail]])*(xp[q[tail]]-xp[q[tail-1]])) tail--;
		q[++tail]=id;
	}

	int query(int i){
		while(head<tail && (yp[q[tail]]-yp[q[tail-1]])<=(xp[q[tail]]-xp[q[tail-1]])*i) tail--;
		return q[tail];
	}
}

void init(){
	for(int i=1;i<=n;i++) s1[i]=a[i]+s1[i-1];
	for(int i=1;i<=n;i++) s2[i]=a[n-i+1]+s2[i-1];
	Convex::init();
	Convex::addPoint(0,0,0);
	for(int i=1;i<=n;i++){
		int j=Convex::query(i);
		f1[i]=max(f1[i-1],f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]));
		pre[i]=j;
		if(f1[i]==f1[i-1]) pre[i]=i;
		Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
	}
	Convex::init();
	Convex::addPoint(0,0,0);
	for(int i=1;i<=n;i++){
		int j=Convex::query(i);
		f2[i]=max(f2[i-1],f2[j]+(LL)(i-j)*(i-j+1)/2-(s2[i]-s2[j]));
		Convex::addPoint(i,i,f2[i]+((LL)i*i-i)/2+s2[i]);
	}
	for(int i=1;i<=n;i++) if(i<n-i+1) swap(f2[i],f2[n-i+1]);
	for(int i=1;i<=n;i++) ans[i]=-(1LL<<60);
}

void gao(int l,int r){
	if(l==r){
		ans[l]=max(ans[l],f1[l-1]+f2[l+1]+1-a[l]);
		return;
	}
	int mid=(l+r)>>1;
	Convex::init();
	for(int i=l-1;i<mid;i++)
		Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
	for(int i=mid+1;i<=r;i++){
		int j=Convex::query(i);
		temp[i]=f2[i+1]+f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]);
	}
	LL tmax=-(1LL<<60);
	for(int i=r;i>mid;i--){
		if(temp[i]>tmax) tmax=temp[i];
		if(tmax>ans[i]) ans[i]=tmax;
	}
	Convex::init();
	for(int i=r+1;i>mid+1;i--){
		int i2=r+1-i;
		Convex::addPoint(i,i2,f2[i]+((LL)i2*i2-i2)/2+s2[n-i+1]);
	}
	for(int i=mid;i>=l;i--){
		int j=Convex::query(r+1-i);
		temp[i]=f1[i-1]+f2[j]+(LL)(j-i)*(j-i+1)/2-(s1[j-1]-s1[i-1]);
	}
	tmax=-(1LL<<60);
	for(int i=l;i<=mid;i++){
		if(temp[i]>tmax) tmax=temp[i];
		if(tmax>ans[i]) ans[i]=tmax;
	}
	gao(l,mid);
	gao(mid+1,r);
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	init();
	gao(1,n);
	scanf("%d",&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		LL ans1=f1[x-1]+f2[x+1];
		LL ans2=ans[x]-y+a[x];
		printf("%lld\n",max(ans1,ans2));
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:101:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:102:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld",a+i);
                                         ^
./Main.cpp:105:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
./Main.cpp:108:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

Judge Result