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