Submission #1696347

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define N 300005
using namespace std;
const int offset=1<<19;
LL mx[(1<<20)+3];
void setmax(int l,int r,LL val){
	l+=offset,r+=offset;
	for(l--,r++;(l^r)!=1;l>>=1,r>>=1){
		if(l&1^1) mx[l^1]=max(mx[l^1],val);
		if(r&1) mx[r^1]=max(mx[r^1],val);
	}
}

int n,t[N];
#define x first
#define y second
int head,tail;
pair<int,LL> q[N];
#define py(k) (f[k]+s[k]+((k)*1LL*(k)-(k))/2)
#define px(k) (k)
#define cross(x1,y1,x2,y2) ((x1)*(y2)-(x2)*(y1))
void solve(LL *s,LL *dp,LL *f,int *ch){
	head=tail=0;//(]
	for(int i=1;i<=n;i++){
		//add i-1 这是个上凸包 
		while(head-tail>1&&cross(px(i-1)-q[head-1].x,py(i-1)-q[head-1].y,
			q[head].x-q[head-1].x,q[head].y-q[head-1].y)<=0) head--;
		q[++head]=make_pair(px(i-1),py(i-1));
		//getans
		while(head-tail>1&&(q[head].y-q[head-1].y)<
			(q[head].x-q[head-1].x)*1LL*i) head--;
		ch[i]=q[head].x;
		dp[i]=py(ch[i])-1LL*ch[i]*i+(i*1LL*i+i)/2-s[i];
		f[i]=max(f[i-1],dp[i]);
	}
}

LL s[N],dp[2][N],f[2][N];int ch[2][N];
void getans(){
	memset(mx,0xc0,sizeof(mx));
	for(int i=1;i<=n;i++)
		setmax(ch[0][i]+1,i,dp[0][i]+f[1][n-i]);
	for(int i=1;i<offset;i++){
		mx[i<<1]=max(mx[i<<1],mx[i]);
		mx[i<<1|1]=max(mx[i<<1|1],mx[i]);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]),s[i]=s[i-1]+t[i];
	solve(s,dp[0],f[0],ch[0]);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+t[n+1-i];
	solve(s,dp[1],f[1],ch[1]);
	getans();
		
	int m;
	scanf("%d",&m);
	for(int i=1,p,x;i<=m;i++){
		scanf("%d%d",&p,&x);
		printf("%lld\n",max(f[0][p-1]+f[1][n-p],mx[p+offset]+t[p]-x));
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:52:58: 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]),s[i]=s[i-1]+t[i];
                                                          ^
./Main.cpp:59:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&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