結果

問題 No.704 ゴミ拾い Medium
ユーザー beetbeet
提出日時 2018-06-15 23:01:44
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 337 ms / 1,500 ms
コード長 2,037 bytes
コンパイル時間 1,684 ms
コンパイル使用メモリ 171,508 KB
実行使用メモリ 28,984 KB
最終ジャッジ日時 2023-09-13 05:07:31
合計ジャッジ時間 11,193 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 3 ms
4,380 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 337 ms
28,700 KB
testcase_25 AC 335 ms
28,716 KB
testcase_26 AC 337 ms
28,804 KB
testcase_27 AC 337 ms
28,736 KB
testcase_28 AC 336 ms
28,984 KB
testcase_29 AC 336 ms
28,708 KB
testcase_30 AC 335 ms
28,704 KB
testcase_31 AC 337 ms
28,644 KB
testcase_32 AC 336 ms
28,912 KB
testcase_33 AC 336 ms
28,744 KB
testcase_34 AC 272 ms
28,856 KB
testcase_35 AC 272 ms
28,788 KB
testcase_36 AC 272 ms
28,780 KB
testcase_37 AC 272 ms
28,708 KB
testcase_38 AC 272 ms
28,708 KB
testcase_39 AC 274 ms
28,704 KB
testcase_40 AC 272 ms
28,924 KB
testcase_41 AC 272 ms
28,696 KB
testcase_42 AC 273 ms
28,720 KB
testcase_43 AC 273 ms
28,708 KB
testcase_44 AC 2 ms
4,376 KB
testcase_45 AC 1 ms
4,380 KB
testcase_46 AC 331 ms
28,780 KB
testcase_47 AC 327 ms
28,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  Int n;
  F f;
  G g;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(Int n_,F f,G g,T ti):
    f(f),g(g),ti(ti){
    init(n_);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(Int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }

  Int find(Int a,Int b,function<bool(T)> &check,Int k,Int l,Int r){
    if(!check(dat[k])||r<=a||b<=l) return -1;
    if(k>=n-1) return k-(n-1);
    Int m=(l+r)>>1;
    Int vl=find(a,b,check,k*2+1,l,m);
    if(~vl) return vl;
    return find(a,b,check,k*2+2,m,r);
  }
  
  Int find(Int a,Int b,function<bool(T)> &check){
    return find(a,b,check,0,0,n);
  }
  
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n),x(n),y(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  for(Int i=0;i<n;i++) cin>>x[i];
  for(Int i=0;i<n;i++) cin>>y[i];

  const Int INF = 1e18;
  auto f=[](Int a,Int b){return min(a,b);};
  SegmentTree<Int, Int> sl(n,f,f,INF);
  SegmentTree<Int, Int> sr(n,f,f,INF);
  vector<Int> dp(n+1,0);
  auto update=
    [&](Int k){      
      if(++k==n) return;
      sl.update(k,dp[k]-x[k]+y[k]);
      sr.update(k,dp[k]+x[k]+y[k]);
    };
  auto query=
    [&](Int k){
      Int t=lower_bound(x.begin(),x.end(),a[k])-x.begin();
      return min(sl.query(0,t)+a[k],sr.query(t,n)-a[k]);
    };
  
  update(-1);
  for(Int i=0;i<n;i++){
    dp[i+1]=query(i);
    update(i);
  }
  
  cout<<dp[n]<<endl;
  return 0;
}
0