結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー 王源成
提出日時 2025-10-22 21:59:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,312 bytes
コンパイル時間 2,290 ms
コンパイル使用メモリ 200,176 KB
実行使用メモリ 31,788 KB
最終ジャッジ日時 2025-10-22 22:00:11
合計ジャッジ時間 14,049 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,INF=1e18;
int n,a[N],x[N],y[N];
struct sugtree{
	#define mid (l+r)/2
	#define ls u<<1
	#define rs u<<1|1
	int mn[N<<2];
	void build(int u,int l,int r){
		mn[u]=INF;
		if(l==r) return;
		build(ls,l,mid);
		build(rs,mid+1,r);
		return;
	}
	void update(int u,int l,int r,int x,int d){
		if(l==r){
			mn[u]=min(mn[u],d);
			return;
		}
		if(x<=mid) update(ls,l,mid,x,d);
		else update(rs,mid+1,r,x,d);
		mn[u]=min(mn[ls],mn[rs]);
		return;
	}
	int query(int u,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return mn[u];
		if(qr<l||r<ql) return INF;
		return min(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
	}
}t[2];
int f[N];
signed main(){
	//freopen("gabbage.in","r",stdin);
	//freopen("gabbage.out","w",stdout); 
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) cin>>y[i];
	f[0]=0;
	t[0].build(1,1,n);t[1].build(1,1,n);
	f[1]=abs(a[1]-x[1])+y[1];
	t[0].update(1,1,n,1,f[0]+y[1]-x[1]);
	t[1].update(1,1,n,1,f[0]+y[1]+x[1]);
	for(int i=2;i<=n;i++){
		int u=lower_bound(x+1,x+1+n,a[i])-x;
		f[i]=min(t[0].query(1,1,n,1,u-1)+a[i],t[1].query(1,1,n,u,i)-a[i]);
		t[0].update(1,1,n,i,f[i-1]+y[i]-x[i]);
		t[1].update(1,1,n,i,f[i-1]+y[i]+x[i]);
	}
	cout<<f[n]<<'\n';
	return 0;
}
0