Submission #1870454

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=300005;
LL q[N],c[N],f[N],g[N],f1[N],f2[N],sum1[N],sum2[N],ans[N];
int a[N],n,m;
void dp(LL *sum){
	memset(f,-0x3f,sizeof f);
	f[0]=0;
	int t=0;q[0]=c[0]=0;
	for (LL i=1;i<=n;i++){
		for (;t && (c[t]-c[t-1])<i*(q[t]-q[t-1]);t--);
		f[i]=max(f[i-1],i*(i+1)/2-sum[i]+c[t]-q[t]*i);
		LL j=f[i]+i*(i-1)/2+sum[i];
		for (;t && (c[t]-c[t-1])*(i-q[t])<(j-c[t])*(q[t]-q[t-1]);t--);
		q[++t]=i;c[t]=j;
	}
}
void dp2(LL *ff,LL *sum,int l,int mid,int r){
	int t=0;
	for (LL i=l-1;i<mid;i++){
		LL j=ff[i]+i*(i-1)/2+sum[i];
		for (;t>1 && (c[t]-c[t-1])*(i-q[t])<(j-c[t])*(q[t]-q[t-1]);t--);
		q[++t]=i;c[t]=j;
	}
	for (LL i=mid+1;i<=r;i++){
		for (;t>1 && (c[t]-c[t-1])<i*(q[t]-q[t-1]);t--);
		f[i]=i*(i+1)/2-sum[i]+c[t]-q[t]*i;
	}
}
void solve(int l,int r){
	if (l==r){
		ans[l]=max(ans[l],f1[l-1]+f2[n-l]+1-a[l]);
		return;
	}
	int mid=(l+r)>>1;
	dp2(f1,sum1,l,mid,r);
	for (int i=r;i>mid;i--) g[i]=f[i]+f2[n-i];
	for (int i=r-1;i>mid;i--) g[i]=max(g[i],g[i+1]);
	dp2(f2,sum2,n-r+1,n-mid,n-l+1);
	for (int i=l;i<=mid;i++) g[i]=f[n-i+1]+f1[i-1];
	for (int i=l+1;i<=mid;i++) g[i]=max(g[i],g[i-1]);
	for (int i=l;i<=r;i++) ans[i]=max(ans[i],g[i]);
	solve(l,mid);solve(mid+1,r);
}
int main(){
	scanf("%d\n",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) sum1[i]=sum1[i-1]+a[i];
	dp(sum1);
	memcpy(f1,f,sizeof f);
	for (int i=1;i<=n;i++) sum2[i]=sum2[i-1]+a[n-i+1];
	dp(sum2);
	memcpy(f2,f,sizeof f);
	solve(1,n);
	scanf("%d\n",&m);
	for (int i=1;i<=m;i++){
		int p,x;
		scanf("%d%d",&p,&x);
		printf("%lld\n",max(f1[p-1]+f2[n-p],ans[p]+a[p]-x));
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&n);
                  ^
./Main.cpp:50:42: 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("%d",&a[i]);
                                          ^
./Main.cpp:58:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&m);
                  ^
./Main.cpp:61:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,&x);
                      ^

Judge Result