义乌中学暑假集训 2021.07.15 D

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(LL x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e6+10;
int n,m,V,a[N],d[N],p[N],stk[N],top,dp[N],Mx,Ans[N],v[N],q[N],w[N],h,t;
LL ans;
vector<pair<int,int> > vis[N];
I void LIS(){
    RI i,j;for(stk[top=1]=a[1],Mx=1,dp[1]=1,i=2;i<=n;i++) if(a[i]>stk[top]) stk[++top]=a[i],dp[i]=top,Mx=max(Mx,top);
    else{RI t=lower_bound(stk+1,stk+top+1,a[i])-stk;dp[i]=t,stk[t]=a[i];}
    for(i=1;i<=n;i++) vis[dp[i]].push_back(make_pair(i,a[i]));
    for(Ans[Mx]=vis[Mx][0].first,i=Mx-1;i>=1;i--){
        RI r=vis[i].size();Ans[i]=2e9;
        for(j=0;j<r;j++) if(vis[i][j].second<a[Ans[i+1]]&&vis[i][j].first<Ans[i]) Ans[i]=vis[i][j].first;
    }for(i=1;i<=Mx;i++) v[Ans[i]]=1;
}
int main(){
    RI i,nd,tg=0;for(read(n),read(m),read(V),i=1;i<=n;i++) read(a[i]);
    for(i=1;i<=n;i++) read(d[i]);for(i=1;i<=n;i++) read(p[i]);
    LIS();for(h=1,t=0,i=1;i<=n;i++){
        if(v[i]) h=t+1;
        W(h<=t&&p[i]-(i-1)*m<=p[q[t]]) t--;
        nd=d[i];W(h<=t) if(nd<w[q[h]]-tg){ans+=1LL*(p[q[h]]+(i-1)*m)*nd,tg+=nd,nd=0;break ;}
        else ans+=1LL*(p[q[h]]+(i-1)*m)*(w[q[h]]-tg),nd-=w[q[h]]-tg,tg=w[q[h++]];
        ans+=1LL*nd*p[i],q[++t]=i,w[i]=V+tg,p[i]-=(i-1)*m;
    }return write(ans),0;
}