#391416 (C++17) No.913 木の燃やし方

提出ソース

結果

問題	No.913 木の燃やし方
ユーザー	beet
提出日時	2019-10-18 23:12:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,899 bytes
コンパイル時間	2,405 ms
コンパイル使用メモリ	208,228 KB
実行使用メモリ	12,420 KB
最終ジャッジ日時	2023-09-08 02:10:17
合計ジャッジ時間	51,211 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	79 ms 4,380 KB
testcase_04	AC	88 ms 4,376 KB
testcase_05	AC	115 ms 4,380 KB
testcase_06	AC	50 ms 4,380 KB
testcase_07	AC	13 ms 4,380 KB
testcase_08	AC	2,220 ms 11,756 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	2,241 ms 12,164 KB
testcase_13	AC	1,578 ms 12,112 KB
testcase_14	AC	1,566 ms 11,996 KB
testcase_15	AC	1,505 ms 12,048 KB
testcase_16	AC	737 ms 11,624 KB
testcase_17	AC	666 ms 11,320 KB
testcase_18	AC	691 ms 11,368 KB
testcase_19	AC	446 ms 11,876 KB
testcase_20	AC	449 ms 11,980 KB
testcase_21	WA	-
testcase_22	AC	1,923 ms 12,064 KB
testcase_23	AC	1,779 ms 12,152 KB
testcase_24	AC	1,720 ms 12,080 KB
testcase_25	AC	430 ms 11,928 KB
testcase_26	AC	1,566 ms 12,388 KB
testcase_27	AC	1,592 ms 12,420 KB
testcase_28	AC	2,274 ms 12,064 KB
testcase_29	AC	2,192 ms 12,156 KB
testcase_30	AC	2,236 ms 12,148 KB
testcase_31	AC	1,559 ms 12,344 KB
testcase_32	AC	1,500 ms 12,284 KB
testcase_33	AC	1,482 ms 12,268 KB
testcase_34	AC	1,484 ms 11,908 KB
testcase_35	AC	1,598 ms 11,944 KB
testcase_36	AC	517 ms 11,836 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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, typename H>
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;


using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// AtCoder
const i64 CYCLES_PER_SEC = 2200000000;

struct Timer {
	i64 start;
	Timer(){reset();}
	void reset(){start=getCycle();}
	inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
	inline i64 getCycle(){
		u32 low,high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((i64)low)|((i64)high<<32);
	}
};

Timer timer;

//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 h=[&](Int a,Int b){return min(a,b);};
  SegmentTree<Int, decltype(h)> seg(h,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 latte=[&](Int k){return uku?n-k:k;};
    auto dist=
      [&](Int i,Int j)->Int{
        if(i<j) return INF;
        Int res=(i-j+1)*(i-j+1)+(sm[i+1]-sm[j]);
        Int l=min(latte(j),latte(i+1));
        Int r=max(latte(j),latte(i+1));
        seg.update(l,r,res);
        return res;
      };
    auto bs=MonotoneMinima::args<Int>(n,dist);
    reverse(as.begin(),as.end());
  }

  {
    vector<Int> ps;
    for(Int i=0;i<n;i++)
      if(as[i]<0) ps.emplace_back(i);
    if(ps.empty()) ps.emplace_back(0);

    Int m=ps.size();
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<Int> ud(0,m-1);

    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;
        Int res=(i-j+1)*(i-j+1)+(sm[i+1]-sm[j]);
        seg.update(j,i+1,res);
        return res;
      };

    if(m<20000){
      for(Int i=0;i<m;i++)
        for(Int j=0;j<i;j++)
          dist(ps[i],ps[j]);
    }else{
      const Int LIM = 1e7 / m;
      for(Int l=1;l<LIM;l++)
        for(Int i=0;i+l<m;i++)
          dist(ps[i+l],ps[i]);
      /*
      for(Int l=1;l<=min((Int)ps.size(),(Int)2000);l++)
        for(Int i=0;i<l;i++)
          seg.update(ps[i],ps[ps.size()-l+i]+1,dist(ps[ps.size()-l+i],ps[i]));
      */
    }
  }

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

yukicoder

結果

テストケース

ソースコード