Submission #1372260


Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int N=5e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int D;
int T[N],x[N];LL y[N],sum[N],f[N],g[N],w[N],pre[N],suf[N];
inline void dp(int n,LL *f) {
	int i,top;
	x[top=1]=0;
	for (i=1;i<=n;i++) {
		sum[i]=sum[i-1]+T[i];
		while (top>1&&y[x[top]]-y[x[top-1]]<=i*(x[top]-x[top-1])) top--;
		f[i]=max(f[i-1],f[x[top]]-sum[i]+sum[x[top]]+1LL*(i-x[top])*(i-x[top]+1)/2);
		y[i]=f[i]+sum[i]+(1LL*i*i-i)/2;
		while (top>1&&(y[i]-y[x[top]])*(x[top]-x[top-1])>=(y[x[top]]-y[x[top-1]])*(i-x[top])) top--;
		x[++top]=i;
	}
}
inline void solve(int l,int r,LL *pre,LL *suf,LL *f) {
	if (l==r) f[l]=1-T[l];
	else {
		int mid=(l+r-D)>>1,i,top=0;
		solve(l,mid,pre,suf,f);
		solve(mid+1,r,pre,suf,f);
		for (i=l-1;i<mid;i++) {
			y[i]=pre[i]+sum[i]+(1LL*i*i-i)/2;
			while (top>1&&(y[i]-y[x[top]])*(x[top]-x[top-1])>=(y[x[top]]-y[x[top-1]])*(i-x[top])) top--;
			x[++top]=i;
		}
		for (i=mid+1;i<=r;i++) {
			while (top>1&&y[x[top]]-y[x[top-1]]<=i*(x[top]-x[top-1])) top--;
			w[i]=pre[x[top]]-sum[i]+sum[x[top]]+1LL*(i-x[top])*(i-x[top]+1)/2+suf[i+1];
		}
		for (i=r-1;i>mid;i--) w[i]=max(w[i],w[i+1]);
		for (i=mid+1;i<=r;i++)
			f[i]=max(f[i],w[i]);
	}
}
int main()
{
	int n=gi(),i,m,t,k;
	for (i=1;i<=n;i++) T[i]=gi();
	dp(n,f);
	reverse(T+1,T+1+n);
	dp(n,g);
	reverse(T+1,T+1+n);
	reverse(g+1,g+1+n);

	for (i=1;i<=n;i++) sum[i]=sum[i-1]+T[i];
	D=0;solve(1,n,f,g,pre);
	reverse(T+1,T+1+n);
	reverse(g+1,g+1+n);
	reverse(f+1,f+1+n);
	for (i=1;i<=n;i++) sum[i]=sum[i-1]+T[i];
	D=1;solve(1,n,g,f,suf);
	reverse(T+1,T+1+n);
	reverse(g+1,g+1+n);
	reverse(f+1,f+1+n);
	reverse(suf+1,suf+1+n);
	
	
	for (m=gi();m--;) {
		k=gi(),t=gi();
		printf("%lld\n",max(f[k-1]+g[k+1],max(pre[k],suf[k])-t+T[k]));
	}
	return 0;
}

Submission Info

Submission Time
Task F - Contest with Drinks Hard
User laofu
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 2155 Byte
Status AC
Exec Time 225 ms
Memory 33280 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 5 ms 16640 KB
sample_02.txt AC 5 ms 16640 KB
subtask_1_high_equaly_01.txt AC 94 ms 30592 KB
subtask_1_high_equaly_02.txt AC 69 ms 28032 KB
subtask_1_high_equaly_03.txt AC 17 ms 16768 KB
subtask_1_high_equaly_04.txt AC 133 ms 30848 KB
subtask_1_high_rand_01.txt AC 91 ms 30464 KB
subtask_1_high_rand_02.txt AC 66 ms 25984 KB
subtask_1_high_rand_03.txt AC 97 ms 30464 KB
subtask_1_high_rand_04.txt AC 124 ms 30720 KB
subtask_1_killer_01.txt AC 4 ms 14592 KB
subtask_1_killer_02.txt AC 4 ms 14592 KB
subtask_1_low_equaly_01.txt AC 155 ms 32128 KB
subtask_1_low_equaly_02.txt AC 91 ms 30976 KB
subtask_1_low_equaly_03.txt AC 103 ms 31360 KB
subtask_1_low_equaly_04.txt AC 51 ms 25856 KB
subtask_1_low_rand_01.txt AC 107 ms 27392 KB
subtask_1_low_rand_02.txt AC 84 ms 28672 KB
subtask_1_low_rand_03.txt AC 70 ms 24448 KB
subtask_1_low_rand_04.txt AC 144 ms 32128 KB
subtask_1_max_high_equaly_01.txt AC 224 ms 32128 KB
subtask_1_max_high_equaly_02.txt AC 222 ms 32384 KB
subtask_1_max_high_equaly_03.txt AC 219 ms 32768 KB
subtask_1_max_high_equaly_04.txt AC 225 ms 31872 KB
subtask_1_max_high_rand_01.txt AC 214 ms 32768 KB
subtask_1_max_high_rand_02.txt AC 212 ms 32128 KB
subtask_1_max_high_rand_03.txt AC 209 ms 32128 KB
subtask_1_max_high_rand_04.txt AC 216 ms 32384 KB
subtask_1_max_low_equaly_01.txt AC 192 ms 33024 KB
subtask_1_max_low_equaly_02.txt AC 186 ms 33280 KB
subtask_1_max_low_equaly_03.txt AC 196 ms 33024 KB
subtask_1_max_low_equaly_04.txt AC 193 ms 33280 KB
subtask_1_max_low_rand_01.txt AC 186 ms 33280 KB
subtask_1_max_low_rand_02.txt AC 195 ms 33024 KB
subtask_1_max_low_rand_03.txt AC 186 ms 33280 KB
subtask_1_max_low_rand_04.txt AC 185 ms 33280 KB
subtask_1_max_rand_equaly_01.txt AC 205 ms 31488 KB
subtask_1_max_rand_equaly_02.txt AC 207 ms 31488 KB
subtask_1_max_rand_equaly_03.txt AC 207 ms 31488 KB
subtask_1_max_rand_equaly_04.txt AC 206 ms 31488 KB
subtask_1_max_rand_rand_01.txt AC 209 ms 31488 KB
subtask_1_max_rand_rand_02.txt AC 225 ms 31488 KB
subtask_1_max_rand_rand_03.txt AC 216 ms 31488 KB
subtask_1_max_rand_rand_04.txt AC 207 ms 31488 KB
subtask_1_min_rand_rand_01.txt AC 4 ms 14592 KB
subtask_1_min_rand_rand_02.txt AC 4 ms 14592 KB
subtask_1_rand_equaly_01.txt AC 11 ms 16768 KB
subtask_1_rand_equaly_02.txt AC 123 ms 30720 KB
subtask_1_rand_equaly_03.txt AC 55 ms 21504 KB
subtask_1_rand_equaly_04.txt AC 99 ms 30336 KB
subtask_1_rand_rand_01.txt AC 146 ms 31232 KB
subtask_1_rand_rand_02.txt AC 84 ms 25984 KB
subtask_1_rand_rand_03.txt AC 130 ms 30976 KB
subtask_1_rand_rand_04.txt AC 58 ms 19328 KB