結果
問題 | No.913 木の燃やし方 |
ユーザー | latte0119 |
提出日時 | 2019-10-18 22:30:25 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 157 ms / 3,000 ms |
コード長 | 3,206 bytes |
コンパイル時間 | 2,200 ms |
コンパイル使用メモリ | 154,540 KB |
実行使用メモリ | 11,764 KB |
最終ジャッジ日時 | 2023-09-08 00:19:48 |
合計ジャッジ時間 | 10,545 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,616 KB |
testcase_01 | AC | 2 ms
5,604 KB |
testcase_02 | AC | 1 ms
5,612 KB |
testcase_03 | AC | 3 ms
5,584 KB |
testcase_04 | AC | 3 ms
5,596 KB |
testcase_05 | AC | 3 ms
5,660 KB |
testcase_06 | AC | 3 ms
5,640 KB |
testcase_07 | AC | 2 ms
5,644 KB |
testcase_08 | AC | 152 ms
8,448 KB |
testcase_09 | AC | 146 ms
8,168 KB |
testcase_10 | AC | 146 ms
8,200 KB |
testcase_11 | AC | 149 ms
8,260 KB |
testcase_12 | AC | 157 ms
8,424 KB |
testcase_13 | AC | 144 ms
8,256 KB |
testcase_14 | AC | 137 ms
8,140 KB |
testcase_15 | AC | 137 ms
8,212 KB |
testcase_16 | AC | 148 ms
8,264 KB |
testcase_17 | AC | 141 ms
8,228 KB |
testcase_18 | AC | 141 ms
8,340 KB |
testcase_19 | AC | 126 ms
11,704 KB |
testcase_20 | AC | 151 ms
8,448 KB |
testcase_21 | AC | 152 ms
8,456 KB |
testcase_22 | AC | 152 ms
8,508 KB |
testcase_23 | AC | 152 ms
9,144 KB |
testcase_24 | AC | 138 ms
10,168 KB |
testcase_25 | AC | 109 ms
11,764 KB |
testcase_26 | AC | 148 ms
8,436 KB |
testcase_27 | AC | 132 ms
10,052 KB |
testcase_28 | AC | 145 ms
8,624 KB |
testcase_29 | AC | 145 ms
8,472 KB |
testcase_30 | AC | 149 ms
8,476 KB |
testcase_31 | AC | 119 ms
9,632 KB |
testcase_32 | AC | 122 ms
9,632 KB |
testcase_33 | AC | 122 ms
9,620 KB |
testcase_34 | AC | 149 ms
8,496 KB |
testcase_35 | AC | 149 ms
8,376 KB |
testcase_36 | AC | 148 ms
8,704 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} template<class A,class B> ostream& operator<<(ostream& ost,const pair<A,B>&p){ ost<<"{"<<p.first<<","<<p.second<<"}"; return ost; } template<class T> ostream& operator<<(ostream& ost,const vector<T>&v){ ost<<"{"; for(int i=0;i<v.size();i++){ if(i)ost<<","; ost<<v[i]; } ost<<"}"; return ost; } template<typename I,bool isMin> struct ConvexHullTrick{ #define a first #define b second using Line=pair<I,I>; deque<Line>lines; //l.a>=m.a>=r.a inline bool notNecessary(const Line &l,const Line &m,const Line &r){ return (m.a-l.a)*(r.b-m.b)>=(m.b-l.b)*(r.a-m.a); } void addLine(I a,I b){ if(!isMin)a*=-1,b*=-1; Line l(a,b); if(lines.empty())lines.push_back(l); else if(lines.front().a<=a){ if(lines.front().a==a){ if(lines.front().b<=b)return; lines.pop_front(); } while(lines.size()>=2&¬Necessary(l,lines[0],lines[1]))lines.pop_front(); lines.push_front(l); } else{ if(lines.back().a==a){ if(lines.back().b<=b)return; lines.pop_back(); } while(lines.size()>=2&¬Necessary(lines[lines.size()-2],lines[lines.size()-1],l))lines.pop_back(); lines.push_back(l); } } inline I eval(const Line &l,I x){ return l.a*x+l.b; } I query(I x){ int lb=-1,ub=lines.size()-1; while(ub-lb>1){ int mid=(ub+lb)/2; if(eval(lines[mid],x)<=eval(lines[mid+1],x))ub=mid; else lb=mid; } if(isMin)return eval(lines[ub],x); return -eval(lines[ub],x); } I queryMonotoneInc(I x){ while(lines.size()>=2&&eval(lines[0],x)>=eval(lines[1],x))lines.pop_front(); if(isMin)return eval(lines[0],x); return -eval(lines[0],x); } I queryMonotoneDec(I x){ while(lines.size()>=2&&eval(lines[lines.size()-1],x)>=eval(lines[lines.size()-2],x))lines.pop_back(); if(isMin)return eval(lines.back(),x); return -eval(lines.back(),x); } #undef a #undef b }; int N; int A[222222]; int S[222222]; int ans[222222]; void solve(int l,int r){ if(r-l<=1)return; int m=(l+r)/2; ConvexHullTrick<int,true>cht; for(int i=l;i<=m;i++){ cht.addLine(-2*i,i*i-S[i]); } int uku=1001001001001001001ll; for(int i=r-1;i>=m;i--){ int tmp=cht.queryMonotoneDec(i+1)+(i+1)*(i+1)+S[i+1]; chmin(uku,tmp); chmin(ans[i],uku); } cht=ConvexHullTrick<int,true>(); for(int i=m;i<r;i++){ cht.addLine(-2*(i+1),(i+1)*(i+1)+S[i+1]); } uku=1001001001001001001ll; for(int i=l;i<=m;i++){ int tmp=cht.queryMonotoneInc(i)+i*i-S[i]; chmin(uku,tmp); chmin(ans[i],uku); } solve(l,m); solve(m+1,r); } signed main(){ scanf("%lld",&N); rep(i,N)scanf("%lld",&A[i]); rep(i,N)S[i+1]=S[i]+A[i]; rep(i,N)ans[i]=1+A[i]; solve(0,N); rep(i,N){ printf("%lld\n",ans[i]); } return 0; }