結果

問題 No.913 木の燃やし方
ユーザー latte0119latte0119
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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&&notNecessary(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&&notNecessary(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;
}
0