WA在了3,4两个点,90分求调
查看原帖
WA在了3,4两个点,90分求调
381053
CQ_Bab楼主2023/10/15 21:24
#include <bits/stdc++.h>
using namespace std ;
#define i12 __int128
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rep1(i,x,y) for(int i=x;i>=y;i--)
#define fire signed
int n,q;
const int N=5e5+10;
int a[N],b[N],c[N];
i12 g[N];
int in[N];
i12 sum[N];
struct node {
	int l,r;
	i12 Min;
} tr[N<<2];
void up(int x) {
	tr[x].Min=min(tr[x*2].Min,tr[x*2+1].Min);
}
void build(int u,int l,int r) {
	tr[u]= {l,r};
	if(l==r) {
		tr[u].Min=a[l]+sum[l+1];
		return ;
	}
	int mid=l+r>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	up(u);
}
int Ans(int u,int l,int r) {
	if(tr[u].l>=l&&tr[u].r<=r) {
		return tr[u].Min;
	}
	int mid=tr[u].l+tr[u].r>>1,res=LONG_LONG_MAX;
	if(mid>=l) res=min(res,Ans(u*2,l,r));
	if(mid<r) res=min(res,Ans(u*2+1,l,r));
	return res;
}
void print(int x) {
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
fire main() {
//	freopen("s.out","r",stdin);
//	freopen("s.in","w",stdout);
	scanf("%lld",&n);
	rep(i,1,n) scanf("%lld",&a[i]);
	rep(i,1,n) scanf("%lld",&b[i]);
	rep(i,1,n) scanf("%lld",&c[i]);
	rep1(i,n,1) sum[i]=sum[i+1]+b[i];
	build(1,1,n);
	i12 ans=LONG_LONG_MAX;
	rep(i,1,n) ans=min(ans,a[i]+sum[i+1]);
	scanf("%lld",&q);
	while(q--) {
		int cnt=false;
		scanf("%lld",&cnt);
		if(!cnt) {
			print(ans);
			cout<<endl;
			continue;
		}
		rep(j,1,cnt) scanf("%lld",&in[j]);
		g[cnt+1]=false;
		rep1(i,cnt,1) g[i]=g[i+1]+b[in[i]];
		i12 res=LONG_LONG_MAX,now=0;
		if(cnt==n) {
			cout<<"0\n";
			continue;
		}
		res=Ans(1,1,in[1]-1)-g[1];
		rep(i,1,cnt) {
			res=min(res,now+Ans(1,in[i-1]+1,in[i]-1)-g[i]);
			now+=c[in[i]];
			res=min(res,now+a[in[i]]+sum[in[i]+1]-g[i+1]);
		}
		res=min(res,now+Ans(1,in[cnt]+1,n));
		print(res);
		cout<<endl;
	}
	return false;
}
/*
7
10 1 6 9 4 2 4
0 5 2 3 0 1 4
4 1 4 1 5 3 5
1
2 2 6
*/
2023/10/15 21:24
加载中...