結果

問題 No.704 ゴミ拾い Medium
ユーザー vjudge1
提出日時 2025-03-20 15:29:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 187 ms / 1,500 ms
コード長 1,683 bytes
コンパイル時間 2,037 ms
コンパイル使用メモリ 193,000 KB
実行使用メモリ 19,328 KB
最終ジャッジ日時 2025-03-20 15:29:11
合計ジャッジ時間 9,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:67:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:68:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:69:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         for(int i=1;i<=n;i++) scanf("%lld",&y[i]);
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const long long inf=1e18;
struct node
{
	int l,r;
	long long mi1;
	long long mi2;
}tr[N<<2];
void pushup(int id)
{
	tr[id].mi1=min(tr[id<<1].mi1,tr[id<<1|1].mi1);
	tr[id].mi2=min(tr[id<<1].mi2,tr[id<<1|1].mi2);
}
void build(int id,int l,int r)
{
	tr[id]={l,r,inf,inf};
	if(l==r) return;
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
}
void change(int id,int x,long long s,long long t)
{
	if(tr[id].l==tr[id].r)
	{
		tr[id].mi1=min(tr[id].mi1,s);
		tr[id].mi2=min(tr[id].mi2,t);
		return;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(x<=mid) change(id<<1,x,s,t);
	else change(id<<1|1,x,s,t);
	pushup(id);
}
long long ask1(int id,int l,int r)
{
	if(l<=tr[id].l&&tr[id].r<=r)
	{
		return tr[id].mi1;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	long long ans=1e18;
	if(l<=mid) ans=min(ans,ask1(id<<1,l,r));
	if(r>mid) ans=min(ans,ask1(id<<1|1,l,r));
	return ans; 
}
long long ask2(int id,int l,int r)
{
	if(l<=tr[id].l&&tr[id].r<=r)
	{
		return tr[id].mi2;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	long long ans=1e18;
	if(l<=mid) ans=min(ans,ask2(id<<1,l,r));
	if(r>mid) ans=min(ans,ask2(id<<1|1,l,r));
	return ans; 
}
long long a[N],x[N],y[N];
long long dp[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&y[i]);
	build(1,0,100000);
	change(1,x[1],y[1]-x[1],y[1]+x[1]);
	for(int i=1;i<=n;i++)
	{

		dp[i]=min(ask1(1,0,a[i])+a[i],ask2(1,a[i],100000)-a[i]);
		//if(i==1) cout<<x[i]<<" "<<dp[i]-x[i]+y[i]<<" "<<dp[i]+x[i]+y[i]<<"\n";
		change(1,x[i+1],dp[i]-x[i+1]+y[i+1],dp[i]+x[i+1]+y[i+1]);
	}
	cout<<dp[n];
}
0