QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#476575 | #9127. Optimal Train Operation | ucup-team3510# | WA | 3ms | 57096kb | C++20 | 2.8kb | 2024-07-13 20:15:45 | 2024-07-13 20:15:45 |
Judging History
answer
#include <bits/stdc++.h>
#define N 500011
#define ll long long
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int n,c[N],a[N];
struct modi{ll v,*id;}md[N*40];int mdn;
void Modi(ll &x,ll y,bool d)
{
if(x==y)return;
if(d){++mdn;md[mdn].v=x;md[mdn].id=&x;}
x=y;
}
struct line
{
ll k,b;
line(){}line(ll _k,ll _b){k=_k;b=_b;}
ll operator()(ll x){return k*x+b;}
};
struct sgt
{
ll lc[N*2],rc[N*2],gn;int gb[N*2];line tr[N*2];
sgt(){for(int i=N*2-1;i;--i)gb[++gn]=i;}
void ins(line l,int L,int R,ll &x,bool d=0)
{
if(L>R)return;//printf("ins(%lldx+%lld,[%d,%d],%lld,%d)\n",l.k,l.b,L,R,x,d);
if(!x)
{
Modi(x,gb[gn],d);
Modi(gn,gn-1,d);
tr[x]=l;lc[x]=rc[x]=0;
return;
}
int mid=L+R>>1;
if(l(mid)<=tr[x](mid))
{
line tt=tr[x];
Modi(tr[x].k,l.k,d);
Modi(tr[x].b,l.b,d);
l=tt;
}
if(l.k<tr[x].k)ins(l,(L+R>>1)+1,R,rc[x],d);
else ins(l,L,L+R>>1,lc[x],d);
}
ll query(int X,int L,int R,int x)
{//printf("query(%d,[%d,%d],%d) (%lldx+%lld)\n",X,L,R,x,tr[x].k,tr[x].b);
if(!x)return 1e18;
if(L==R)return tr[x](X);
ll ans=tr[x](X);
if(X<=L+R>>1)return min(ans,query(X,L,L+R>>1,lc[x]));
else return min(ans,query(X,(L+R>>1)+1,R,rc[x]));
}
int merge(ll x,int y,int L,int R)
{//printf("merge(%lld,%d,[%d,%d])\n",x,y,L,R);
if(!x||!y)return x^y;
lc[x]=merge(lc[x],lc[y],L,L+R>>1);
rc[x]=merge(rc[x],rc[y],(L+R>>1)+1,R);
gb[++gn]=y;ins(tr[y],L,R,x);
return x;
}
}T1,T2;
pii mx[21][N];
ll f[N];int lg[N];
pii query(int l,int r)
{
int logl=lg[r-l+1];
return max(mx[logl][l],mx[logl][r-(1<<logl)+1]);
}
int lc[N*2],rc[N*2],sz;ll rt1[N*2],rt2;
void solve(int L,int R,int &x)
{
if(!x)x=++sz;
// printf("solve([%d,%d],%d)\n",L,R,x);
if(L==R)
{
if(L)f[L]=T2.query(L,0,n,1)+a[L];
T1.ins(line(-L,f[L]),-1e9,-1,rt1[x]);
return;
}
int tmdn=mdn;
int M=query(L,R-1).s2;
solve(L,M,lc[x]);
int c=::c[M];
ll val=T1.query(c,-1e9,-1,rt1[lc[x]]);
// printf("[%d,%d] M:%d c:%d val:%lld\n",L,R,M,c,val);
T2.ins(line(c,val),1,n,rt2,1);
solve(M+1,R,rc[x]);
rt1[x]=T1.merge(rt1[lc[x]],rt1[rc[x]],-1e9,-1);//printf("rt1[%d,%d]:%d\n",L,R,rt1[x]);
while(mdn>tmdn)*md[mdn].id=md[mdn].v,--mdn;
}
int rt;
int main()
{
// freopen("O.in","r",stdin);freopen("O.out","w",stdout);setvbuf(stdout,0,_IONBF,0);
scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%d",c+i);
for(int i=1;i<n;++i)scanf("%d",a+i);
for(int i=0;i<n;++i)mx[0][i]=pii(c[i],i);
for(int i=1;i<=20;++i)for(int j=0;j+(1<<i)-1<n;++j)mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
lg[0]=-1;for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1;
solve(0,n,rt);
// printf("f:");for(int i=0;i<=n;++i)printf("%lld ",f[i]);putchar(10);
printf("%lld\n",f[n]);
fclose(stdin);fclose(stdout);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 35636kb
input:
4 3 1 4 1 5 9 2
output:
15
result:
ok "15"
Test #2:
score: 0
Accepted
time: 0ms
memory: 34700kb
input:
9 28 35 19 27 84 98 78 79 60 40 35 54 63 72 71 27 94
output:
682
result:
ok "682"
Test #3:
score: 0
Accepted
time: 3ms
memory: 33932kb
input:
7 476190629 262703497 211047202 971407775 628894325 731963982 822804784 877914575 602436426 24979445 861648772 623690081 433933447
output:
5339182432
result:
ok "5339182432"
Test #4:
score: 0
Accepted
time: 3ms
memory: 35708kb
input:
8 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 430302156 982631932 161735902 880895728 923078537 707723857 189330739
output:
6166732840
result:
ok "6166732840"
Test #5:
score: 0
Accepted
time: 0ms
memory: 32908kb
input:
5 191890310 576823355 782177068 404011431 818008580 839296263 462224593 492601449 384836991
output:
4069897043
result:
ok "4069897043"
Test #6:
score: 0
Accepted
time: 0ms
memory: 34424kb
input:
6 138996221 501899080 353195922 545531545 910748511 350034067 160449218 155374934 840594328 164163676 797829355
output:
3921700772
result:
ok "3921700772"
Test #7:
score: 0
Accepted
time: 3ms
memory: 33760kb
input:
2 824284691 533206504 470338674
output:
1648569382
result:
ok "1648569382"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 57096kb
input:
4524 43 144 216 44 156 252 243 172 78 246 56 103 207 177 102 22 202 236 61 255 128 238 237 187 176 110 156 213 65 11 75 239 142 9 203 124 154 149 119 59 152 91 151 226 131 184 174 236 220 149 16 209 51 32 40 131 119 138 201 171 249 150 108 82 75 70 204 80 131 42 180 125 257 131 5 107 39 145 154 242 ...
output:
1161280
result:
wrong answer 1st words differ - expected: '892773', found: '1161280'