結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー beet
提出日時 2018-06-15 23:01:44
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 353 ms / 1,500 ms
コード長 2,037 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,853 ms
コンパイル使用メモリ 174,588 KB
実行使用メモリ 29,140 KB
最終ジャッジ日時 2024-06-30 15:18:27
合計ジャッジ時間 10,689 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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