Submission #1869587


Source Code Expand

#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 300010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,q;

int t[maxn];

int Q[maxn],top;

ll sm[maxn],f[maxn],y[maxn],pre[maxn],suf[maxn],tmp[maxn],Ans[maxn];

void DP(){
	REP(i,1,n)sm[i]=sm[i-1]+t[i];
	Q[top=1]=0;
	REP(i,1,n){
		f[i]=f[i-1];
		while(top>1&&(y[Q[top]]-y[Q[top-1]])<=2ll*i*(Q[top]-Q[top-1]))top--;
		f[i]=max(f[i],f[Q[top]]+1ll*(i-Q[top])*(i-Q[top]+1)/2+sm[Q[top]]-sm[i]);
		y[i]=f[i]*2+1ll*i*i-i+sm[i]*2;
		while(top>1&&(y[Q[top]]-y[Q[top-1]])*(i-Q[top])<=(y[i]-y[Q[top]])*(Q[top]-Q[top-1]))top--;
		Q[++top]=i;
	}
}

void solve(int l,int r){
//	cout<<l<<' '<<r<<endl;
	if(l==r){
		Ans[l]=max(Ans[l],pre[l-1]+suf[l+1]+1-t[l]);
		return;
	}
	int M=l+r>>1;
	top=0;
	REP(i,l-1,M-1){
		y[i]=pre[i]*2+1ll*i*i-i+sm[i]*2;
		while(top>1&&(y[Q[top]]-y[Q[top-1]])*(i-Q[top])<=(y[i]-y[Q[top]])*(Q[top]-Q[top-1]))top--;
		Q[++top]=i;
	}
	REP(i,M,r){
		while(top>1&&(y[Q[top]]-y[Q[top-1]])<=2ll*i*(Q[top]-Q[top-1]))top--;
		tmp[i]=pre[Q[top]]+suf[i+1]+1ll*(i-Q[top])*(i-Q[top]+1)/2+sm[Q[top]]-sm[i];
	}
	RREP(i,r-1,M)tmp[i]=max(tmp[i],tmp[i+1]);
//	REP(i,M+1,r)cout<<tmp[i]<<' ';cout<<endl;
	REP(i,M,r)Ans[i]=max(Ans[i],tmp[i]);
	solve(l,M);solve(M+1,r);
	
}

void Work(){
	read(q);
	while(q--){
		int p,x;read(p,x);
		ll ans=max(pre[p-1]+suf[p+1],Ans[p]-x+t[p]);
		printf("%lld\n",ans);
	}
}

void Init(){
	read(n);
	REP(i,1,n)read(t[i]);
	DP();REP(i,1,n)pre[i]=f[i];
	reverse(t+1,t+n+1);
	DP();REP(i,1,n)suf[i]=f[i];
	reverse(t+1,t+n+1);reverse(suf+1,suf+n+1);
	
//	REP(i,1,n)cout<<pre[i]<<' ';cout<<endl;
//	REP(i,1,n)cout<<suf[i]<<' ';cout<<endl;
	
	REP(i,1,n)Ans[i]=-t[i],sm[i]=sm[i-1]+t[i];	
	solve(1,n);
	reverse(t+1,t+n+1);REP(i,1,n)sm[i]=sm[i-1]+t[i];
	reverse(pre+1,pre+n+1);reverse(suf+1,suf+n+1);reverse(Ans+1,Ans+n+1);REP(i,1,n)swap(pre[i],suf[i]);
	solve(1,n);
	reverse(t+1,t+n+1);REP(i,1,n)sm[i]=sm[i-1]+t[i];
	reverse(pre+1,pre+n+1);reverse(suf+1,suf+n+1);reverse(Ans+1,Ans+n+1);REP(i,1,n)swap(pre[i],suf[i]);
}

int main(){
	Init();
	Work();
	return 0;
}

Submission Info

Submission Time
Task F - Contest with Drinks Hard
User yanQval
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 3632 Byte
Status AC
Exec Time 261 ms
Memory 21376 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 2
AC × 54
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt
Case Name Status Exec Time Memory
sample_01.txt AC 4 ms 14592 KB
sample_02.txt AC 4 ms 14592 KB
subtask_1_high_equaly_01.txt AC 96 ms 18176 KB
subtask_1_high_equaly_02.txt AC 72 ms 17792 KB
subtask_1_high_equaly_03.txt AC 16 ms 14720 KB
subtask_1_high_equaly_04.txt AC 131 ms 18560 KB
subtask_1_high_rand_01.txt AC 94 ms 18176 KB
subtask_1_high_rand_02.txt AC 67 ms 17792 KB
subtask_1_high_rand_03.txt AC 96 ms 18176 KB
subtask_1_high_rand_04.txt AC 120 ms 18432 KB
subtask_1_killer_01.txt AC 4 ms 12544 KB
subtask_1_killer_02.txt AC 3 ms 12544 KB
subtask_1_low_equaly_01.txt AC 136 ms 19840 KB
subtask_1_low_equaly_02.txt AC 96 ms 18688 KB
subtask_1_low_equaly_03.txt AC 108 ms 19200 KB
subtask_1_low_equaly_04.txt AC 53 ms 17664 KB
subtask_1_low_rand_01.txt AC 103 ms 19200 KB
subtask_1_low_rand_02.txt AC 84 ms 18432 KB
subtask_1_low_rand_03.txt AC 69 ms 18304 KB
subtask_1_low_rand_04.txt AC 133 ms 19840 KB
subtask_1_max_high_equaly_01.txt AC 216 ms 20224 KB
subtask_1_max_high_equaly_02.txt AC 216 ms 20480 KB
subtask_1_max_high_equaly_03.txt AC 219 ms 20736 KB
subtask_1_max_high_equaly_04.txt AC 211 ms 19840 KB
subtask_1_max_high_rand_01.txt AC 213 ms 20736 KB
subtask_1_max_high_rand_02.txt AC 213 ms 20224 KB
subtask_1_max_high_rand_03.txt AC 220 ms 20224 KB
subtask_1_max_high_rand_04.txt AC 213 ms 20480 KB
subtask_1_max_low_equaly_01.txt AC 187 ms 20992 KB
subtask_1_max_low_equaly_02.txt AC 188 ms 21376 KB
subtask_1_max_low_equaly_03.txt AC 194 ms 20992 KB
subtask_1_max_low_equaly_04.txt AC 190 ms 21376 KB
subtask_1_max_low_rand_01.txt AC 190 ms 21376 KB
subtask_1_max_low_rand_02.txt AC 194 ms 20992 KB
subtask_1_max_low_rand_03.txt AC 189 ms 21376 KB
subtask_1_max_low_rand_04.txt AC 187 ms 21376 KB
subtask_1_max_rand_equaly_01.txt AC 215 ms 19584 KB
subtask_1_max_rand_equaly_02.txt AC 217 ms 19584 KB
subtask_1_max_rand_equaly_03.txt AC 211 ms 19584 KB
subtask_1_max_rand_equaly_04.txt AC 212 ms 19584 KB
subtask_1_max_rand_rand_01.txt AC 261 ms 19584 KB
subtask_1_max_rand_rand_02.txt AC 217 ms 19584 KB
subtask_1_max_rand_rand_03.txt AC 210 ms 19584 KB
subtask_1_max_rand_rand_04.txt AC 212 ms 19584 KB
subtask_1_min_rand_rand_01.txt AC 4 ms 12544 KB
subtask_1_min_rand_rand_02.txt AC 4 ms 12544 KB
subtask_1_rand_equaly_01.txt AC 10 ms 14720 KB
subtask_1_rand_equaly_02.txt AC 125 ms 18432 KB
subtask_1_rand_equaly_03.txt AC 56 ms 17408 KB
subtask_1_rand_equaly_04.txt AC 100 ms 18048 KB
subtask_1_rand_rand_01.txt AC 151 ms 19072 KB
subtask_1_rand_rand_02.txt AC 86 ms 17792 KB
subtask_1_rand_rand_03.txt AC 136 ms 18816 KB
subtask_1_rand_rand_04.txt AC 57 ms 17280 KB