Submission #1696140
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[tail+2].y-q[tail+1].y)>
(q[tail+2].x-q[tail+1].x)*1LL*i) tail++;
ch[i]=q[tail+1].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(){
for(int i=1;i<=n;i++)
setmax(ch[0][i],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
Submission Time |
|
Task |
F - Contest with Drinks Hard |
User |
Wuvin |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1599 Byte |
Status |
WA |
Exec Time |
165 ms |
Memory |
29056 KB |
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
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
9 ms |
22268 KB |
sample_02.txt |
AC |
8 ms |
22272 KB |
subtask_1_high_equaly_01.txt |
WA |
59 ms |
23680 KB |
subtask_1_high_equaly_02.txt |
WA |
42 ms |
23296 KB |
subtask_1_high_equaly_03.txt |
WA |
27 ms |
22656 KB |
subtask_1_high_equaly_04.txt |
WA |
117 ms |
23936 KB |
subtask_1_high_rand_01.txt |
WA |
63 ms |
23680 KB |
subtask_1_high_rand_02.txt |
WA |
48 ms |
23168 KB |
subtask_1_high_rand_03.txt |
WA |
69 ms |
23680 KB |
subtask_1_high_rand_04.txt |
WA |
99 ms |
23936 KB |
subtask_1_killer_01.txt |
AC |
8 ms |
22272 KB |
subtask_1_killer_02.txt |
AC |
8 ms |
22272 KB |
subtask_1_low_equaly_01.txt |
WA |
122 ms |
24192 KB |
subtask_1_low_equaly_02.txt |
WA |
60 ms |
24192 KB |
subtask_1_low_equaly_03.txt |
WA |
69 ms |
24320 KB |
subtask_1_low_equaly_04.txt |
WA |
35 ms |
23168 KB |
subtask_1_low_rand_01.txt |
WA |
103 ms |
23552 KB |
subtask_1_low_rand_02.txt |
WA |
67 ms |
23552 KB |
subtask_1_low_rand_03.txt |
WA |
64 ms |
23168 KB |
subtask_1_low_rand_04.txt |
WA |
120 ms |
24704 KB |
subtask_1_max_high_equaly_01.txt |
WA |
161 ms |
24832 KB |
subtask_1_max_high_equaly_02.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_high_equaly_03.txt |
WA |
161 ms |
24832 KB |
subtask_1_max_high_equaly_04.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_high_rand_01.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_high_rand_02.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_high_rand_03.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_high_rand_04.txt |
WA |
165 ms |
24832 KB |
subtask_1_max_low_equaly_01.txt |
WA |
154 ms |
24832 KB |
subtask_1_max_low_equaly_02.txt |
WA |
153 ms |
25088 KB |
subtask_1_max_low_equaly_03.txt |
WA |
162 ms |
24832 KB |
subtask_1_max_low_equaly_04.txt |
WA |
161 ms |
25472 KB |
subtask_1_max_low_rand_01.txt |
WA |
158 ms |
25472 KB |
subtask_1_max_low_rand_02.txt |
WA |
158 ms |
24832 KB |
subtask_1_max_low_rand_03.txt |
WA |
155 ms |
24832 KB |
subtask_1_max_low_rand_04.txt |
WA |
153 ms |
25728 KB |
subtask_1_max_rand_equaly_01.txt |
WA |
138 ms |
28928 KB |
subtask_1_max_rand_equaly_02.txt |
WA |
138 ms |
28928 KB |
subtask_1_max_rand_equaly_03.txt |
WA |
137 ms |
28928 KB |
subtask_1_max_rand_equaly_04.txt |
WA |
138 ms |
28928 KB |
subtask_1_max_rand_rand_01.txt |
WA |
140 ms |
29056 KB |
subtask_1_max_rand_rand_02.txt |
WA |
143 ms |
28928 KB |
subtask_1_max_rand_rand_03.txt |
WA |
142 ms |
28928 KB |
subtask_1_max_rand_rand_04.txt |
WA |
160 ms |
28928 KB |
subtask_1_min_rand_rand_01.txt |
AC |
8 ms |
22272 KB |
subtask_1_min_rand_rand_02.txt |
AC |
8 ms |
22272 KB |
subtask_1_rand_equaly_01.txt |
WA |
16 ms |
22400 KB |
subtask_1_rand_equaly_02.txt |
WA |
91 ms |
26112 KB |
subtask_1_rand_equaly_03.txt |
WA |
50 ms |
24960 KB |
subtask_1_rand_equaly_04.txt |
WA |
64 ms |
27776 KB |
subtask_1_rand_rand_01.txt |
WA |
78 ms |
28416 KB |
subtask_1_rand_rand_02.txt |
WA |
69 ms |
25472 KB |
subtask_1_rand_rand_03.txt |
WA |
68 ms |
28288 KB |
subtask_1_rand_rand_04.txt |
WA |
65 ms |
24960 KB |