結果
問題 | No.704 ゴミ拾い Medium |
ユーザー |
![]() |
提出日時 | 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]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#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]; }