Submission #1693085

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long  LL;
const int N=300010;
int n,m,t[N],q[N];
LL a[N],sum[N],l[N],r[N],f[N];

void calc(LL *f)
{
	LL sum=0;
	for (int i=1,top=0,pos=0; i<=n; i++)
		{
			sum+=t[i],pos=min(pos+1,top);
			while ((pos)&&(a[q[pos]]-1LL*q[pos]*i<a[q[pos-1]]-1LL*q[pos-1]*i))  pos--;
			f[i]=max(f[i-1],a[q[pos]]-1LL*q[pos]*i+1LL*i*(i+1)/2-sum);
			a[i]=f[i]+1LL*i*(i-1)/2+sum;
			while ((top)&&((a[i]-a[q[top]])*(q[top]-q[top-1])-(a[q[top]]-a[q[top-1]])*(i-q[top])>=0))  top--;
			q[++top]=i;
		}
}

void solve(int L,int R,int ty)
{
	if (L==R)  {f[L]=max(f[L],l[L-1]+r[L+1]+1-t[L]);  return;}
	int mid=(L+R-ty)>>1,top=0;  LL mx=-1LL<<60;
	solve(L,mid,ty),solve(mid+1,R,ty);
	for (int i=L-1; i<=mid; i++)
		{
			a[i]=l[i]+sum[i]+1LL*i*(i-1)/2;
			while ((top>1)&&((a[i]-a[q[top]])*(q[top]-q[top-1])-(a[q[top]]-a[q[top-1]])*(i-q[top])>=0))  top--;
			q[++top]=i;
		}
	for (int i=R,pos=1; i>mid; i--)
		{
			while ((pos<top)&&(a[q[pos]]-1LL*q[pos]*i<a[q[pos+1]]-1LL*q[pos+1]*i))  pos++;
			mx=max(mx,a[q[pos]]-1LL*q[pos]*i+1LL*i*(i+1)/2-sum[i]+r[i+1]);
			f[i]=max(f[i],mx);
		}
}

void work()
{
	scanf("%d",&n);
	for (int i=1; i<=n; i++)  scanf("%d",&t[i]),f[i]=-1LL<<60;
	calc(l),reverse(t+1,t+n+1);
	calc(r),reverse(t+1,t+n+1),reverse(r+1,r+n+1);
	for (int i=1; i<=n; i++)  sum[i]=sum[i-1]+t[i];
	solve(1,n,0);
	reverse(t+1,t+n+1),reverse(f+1,f+n+1);
	reverse(l+1,l+n+1),reverse(r+1,r+n+1),swap(l,r);
	for (int i=1; i<=n; i++)  sum[i]=sum[i-1]+t[i];
	solve(1,n,1);
	reverse(t+1,t+n+1),reverse(f+1,f+n+1);
	swap(l,r),reverse(l+1,l+n+1),reverse(r+1,r+n+1);
	scanf("%d",&m);
	for (int i=1,p,x; i<=m; i++)
		scanf("%d %d",&p,&x),printf("%lld\n",max(l[p-1]+r[p+1],f[p]+t[p]-x));
}

int main()
{
	work();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void work()’:
./Main.cpp:44:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:45:59: 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",&t[i]),f[i]=-1LL<<60;
                                                           ^
./Main.cpp:56:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
./Main.cpp:58:71: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&p,&x),printf("%lld\n",max(l[p-1]+r[p+1],f[p]+t[p]-x));
                                                                       ^

Judge Result