結果
問題 | No.913 木の燃やし方 |
ユーザー |
![]() |
提出日時 | 2019-10-20 05:14:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 459 ms / 3,000 ms |
コード長 | 2,723 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 74,728 KB |
実行使用メモリ | 23,168 KB |
最終ジャッジ日時 | 2024-06-28 14:31:39 |
合計ジャッジ時間 | 13,598 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#define llint long long#define inf 1e18using namespace std;typedef pair<llint, llint> P;struct LiChaoTree{int size;vector<P> seg;vector<llint> x;LiChaoTree(){}LiChaoTree(int size){this->size = size;seg.resize(1<<(size+1));x.resize(1<<size);}void init(){for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(0, inf);for(int i = 0; i < (1<<size); i++) x[i] = i; //オーバーフローに注意}llint calc(P f, llint x){return f.first * x + f.second;}llint query(int i) //x[i]における最小値を取得{llint X = x[i], ret = inf;i += (1 << size);while(i >= 1){ret = min(ret, calc(seg[i], X));i /= 2;}return ret;}void add(int k, int l, int r, P f){int m = (l+r)/2;if(calc(f, x[m]) < calc(seg[k], x[m])) swap(seg[k], f);bool L = (calc(f, x[l]) < calc(seg[k], x[l])), R = (calc(f, x[r]) < calc(seg[k], x[r]));if(L == R) return;if(L) add(k*2, l, m, f);if(R) add(k*2+1, m+1, r, f);}void addSegment(int a, int b, int k, int l, int r, P f){if(b < l || r < a) return;if(a <= l && r <= b){add(k, l, r, f);return;}addSegment(a, b, k*2, l, (l+r)/2, f);addSegment(a, b, k*2+1, (l+r)/2+1, r, f);}void addSegment(int a, int b, llint p, llint q) //区間[x[a], x[b]]に線分px+qを追加{addSegment(a, b, 1, 0, (1<<size)-1, make_pair(p, q));}void addLine(llint p, llint q) //直線px+qを追加{return addSegment(0, (1<<size)-1, p, q);}};llint n;llint a[200005], s[200005];LiChaoTree lct;llint ans[200005];void calc(llint l, llint r){if(l > r) return;if(l == r){ans[l] = min(ans[l], s[r]-s[l-1] + 1);return;}llint m = (l+r)/2;llint size = 0;for(int len = r-l+2; len; len/=2) size++;lct = LiChaoTree(size);lct.init();for(int i = 0; i < (1<<size); i++) lct.x[i] = l-1+i;for(llint i = l-1; i < m; i++) lct.addLine(-2*i, i*i-s[i]);llint mn = inf;for(llint i = r; i >= m+1; i--){mn = min(mn, lct.query(i-(l-1)) + i*i + s[i]);ans[i] = min(ans[i], mn);}lct.init();for(int i = 0; i < (1<<size); i++) lct.x[i] = l-1+i;for(llint i = m+1; i <= r; i++) lct.addLine(-2*i, i*i+s[i]);mn = inf;for(llint i = l-1; i < m; i++){mn = min(mn, lct.query(i-(l-1)) + (i*i - s[i]) );ans[i+1] = min(ans[i+1], mn);}calc(l, m);calc(m+1, r);}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];for(int i = 1; i <= n; i++) ans[i] = inf;calc(1, n);for(int i = 1; i <= n; i++) cout << ans[i] << "\n";flush(cout);return 0;}