結果

問題 No.913 木の燃やし方
ユーザー beetbeet
提出日時 2019-10-18 22:29:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,825 bytes
コンパイル時間 2,329 ms
コンパイル使用メモリ 208,372 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2024-06-25 17:37:13
合計ジャッジ時間 82,239 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 30 ms
5,376 KB
testcase_06 WA -
testcase_07 AC 11 ms
5,376 KB
testcase_08 AC 2,596 ms
11,776 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2,668 ms
11,904 KB
testcase_13 AC 2,607 ms
11,852 KB
testcase_14 AC 2,504 ms
11,532 KB
testcase_15 AC 2,501 ms
11,660 KB
testcase_16 AC 2,552 ms
11,900 KB
testcase_17 AC 2,435 ms
11,668 KB
testcase_18 AC 2,440 ms
11,528 KB
testcase_19 AC 2,649 ms
12,032 KB
testcase_20 AC 2,616 ms
11,900 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 2,622 ms
11,904 KB
testcase_24 AC 2,620 ms
11,900 KB
testcase_25 AC 2,611 ms
12,032 KB
testcase_26 AC 2,706 ms
12,028 KB
testcase_27 AC 2,695 ms
11,904 KB
testcase_28 AC 2,675 ms
12,024 KB
testcase_29 AC 2,676 ms
11,904 KB
testcase_30 AC 2,673 ms
11,900 KB
testcase_31 AC 2,674 ms
11,904 KB
testcase_32 AC 2,688 ms
12,024 KB
testcase_33 AC 2,679 ms
12,032 KB
testcase_34 AC 2,661 ms
11,904 KB
testcase_35 AC 2,654 ms
11,904 KB
testcase_36 AC 2,620 ms
12,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


namespace MonotoneMinima{
  template<typename T,typename F>
  void induce(Int l,Int r,Int a,Int b,vector<Int> &dp,F dist){
    if(l==r) return;
    Int m=(l+r)>>1;
    Int &idx=(dp[m]=a);
    T res=dist(idx,m);
    for(Int i=a;i<b;i++){
      T tmp=dist(i,m);
      if(tmp<res) res=tmp,idx=i;
    }
    induce<T>(l,m,a,idx+1,dp,dist);
    induce<T>(m+1,r,idx,b,dp,dist);
  }

  template<typename T,typename F>
  vector<Int> args(Int n,F dist){
    vector<Int> dp(n,-1);
    induce<T>(0,n,0,n,dp,dist);
    return dp;
  }
}


template <typename E>
struct SegmentTree{
  using H = function<E(E,E)>;
  Int n,height;
  H h;
  E ei;
  vector<E> laz;
  SegmentTree(H h,E ei):h(h),ei(ei){}
  void init(Int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    laz.assign(2*n,ei);
  }
  inline void eval(Int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    laz[k]=ei;
  }
  inline void thrust(Int k){
    for(Int i=height;i;i--) eval(k>>i);
  }
  void update(Int a,Int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
  }
  E get_val(Int a){
    thrust(a+=n);
    return laz[a];
  }
  void set_val(Int a,E x){
    thrust(a+=n);
    laz[a]=x;
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

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

  const Int INF = 1e18;
  auto g=[&](Int a,Int b){return min(a,b);};
  SegmentTree<Int> seg(g,INF);
  seg.init(n);

  for(Int uku=0;uku<2;uku++){
    vector<Int> sm(n+1,0);
    for(Int i=0;i<n;i++) sm[i+1]=sm[i]+as[i];

    auto dist=
      [&](Int i,Int j)->Int{
        if(i<j) return INF;
        return (i-j+1)*(i-j+1)+(sm[i+1]-sm[j]);
      };
    auto bs=MonotoneMinima::args<Int>(n,dist);

    auto latte=[&](Int k){return uku?n-k:k;};
    for(Int i=0;i<n;i++){
      Int l=min(latte(i),latte(bs[i]+1));
      Int r=max(latte(i),latte(bs[i]+1));
      seg.update(l,r,dist(bs[i],i));
    }
    reverse(as.begin(),as.end());
  }

  {
    vector<Int> sm(n+1,0);
    for(Int i=0;i<n;i++) sm[i+1]=sm[i]+as[i];

    auto dist=
      [&](Int i,Int j)->Int{
        if(i<j) return INF;
        return (i-j+1)*(i-j+1)+(sm[i+1]-sm[j]);
      };

    const int BS = 100;
    for(int i=0;i<n;i++)
      for(int l=1;l<BS&&i+l<=n;l++)
        seg.update(i,i+l,dist(i+l-1,i));
  }

  for(Int i=0;i<n;i++)
    cout<<seg.get_val(i)<<"\n";
  cout<<flush;
  return 0;
}
0