模拟赛t1 95求调,wa最后一个
查看原帖
模拟赛t1 95求调,wa最后一个
439000
User439000楼主2023/10/19 11:59
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[600005],b[600005],c[600005],temp[600005],c1[600005],b1[600005],q;
struct nb{
long long data,point;
}f[600005][35];
void st(){
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++)
    for(int i=1;i<=n-(1<<j)+1;i++)
            if(f[i][j-1].data<f[i+(1<<(j-1))][j-1].data)
            {
                f[i][j].data=f[i][j-1].data;
                f[i][j].point=f[i][j-1].point;
            }
            else{
                 f[i][j].data=f[i+(1<<(j-1))][j-1].data;
                f[i][j].point=f[i+(1<<(j-1))][j-1].point;
            }
}
long long tell(int l,int r){
int t=log(r-l+1)/log(2);
if(f[l][t].data<f[r-(1<<t)+1][t].data)
    return f[l][t].point;
else return f[r-(1<<t)+1][t].point;
}

long long ask(int tempb[],int tempc[],int sum){
for(int i=1;i<=sum;i++)
{
    scanf("%lld",&temp[i]);
    tempb[temp[i]]=tempb[temp[i-1]]+b[temp[i]];
    tempc[temp[i]]=tempc[temp[i-1]]+c[temp[i]];
}

long long ans=1e18;
for(int j=1;j<=sum;j++){
        int r=temp[j];
        int l=temp[j-1]+1;
        int val=tell(l,r);
        if(val!=r)
    ans=min(ans,f[val][0].data+tempc[r]-c[r]-tempb[temp[m]]+tempb[r]-b[r]);
    else ans=min(ans,f[val][0].data+tempc[r]-tempb[temp[m]]+tempb[r]);
}
ans=min(ans,b1[n]-tempb[temp[m]]);
if(m+1<=n)
{
    int val=tell(m+1,n);
    ans=min(ans,f[val][0].data+tempc[temp[m]]);
}
return ans;
}
int main(){
    int temp1[500001],temp2[500001];
    memset(temp1,0,sizeof(temp1));
    memset(temp2,0,sizeof(temp2));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        b1[i]=b1[i-1]+b[i];
    }
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)
     {
            f[i][0].data=a[i]+b1[n]-b1[i];
            //cout<< f[i][0].data<<endl;
            f[i][0].point=i;
     }
     st();
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&m);
        printf("%lld\n",ask(temp1,temp2,m));
    }
    return 0;
}

2023/10/19 11:59
加载中...