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 |
|
|
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 |