結果

問題 No.913 木の燃やし方
コンテスト
ユーザー ats5515
提出日時 2019-10-18 21:55:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,575 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 104,480 KB
実行使用メモリ 43,832 KB
最終ジャッジ日時 2024-06-25 15:57:23
合計ジャッジ時間 20,312 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <assert.h>
using namespace std;
#define int long long
template <typename T, bool isMin>
struct ConvexHullTrickWithIndex {
	struct P {
		T m, b;
		int idx;
		P(T m, T b, int idx) :m(m), b(b), idx(idx) {};
		bool operator<(const P &a) {
			return m != a.m ? m < a.m : b < a.b;
		}
	};

	deque<P> H;
	bool empty()const { return H.empty(); }
	void clear() { H.clear(); }

	inline int sgn(T x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); }

	using D = long double;
	inline bool check(const P &a, const P &b, const P &c) {
		if (b.b == a.b || c.b == b.b)
			return sgn(b.m - a.m)*sgn(c.b - b.b) >= sgn(c.m - b.m)*sgn(b.b - a.b);
		return D(b.m - a.m)*sgn(c.b - b.b) / D(abs(b.b - a.b))
			>= D(c.m - b.m)*sgn(b.b - a.b) / D(abs(c.b - b.b));
	}

	void addLine(T m, T b, int idx) {
		if (!isMin) m *= -1, b *= -1;
		P line(m, b, idx);
		if (empty()) {
			H.emplace_front(line);
			return;
		}

		if (empty() || H.front().m <= m) {
			if (H.front().m == m) {
				if (H.front().b <= b) return;
				H.pop_front();
			}
			while (H.size() >= 2 && check(line, H.front(), H[1])) H.pop_front();
			H.emplace_front(line);
		}
		else {
			assert(m <= H.back().m);
			if (H.back().m == m) {
				if (H.back().b <= b) return;
				H.pop_back();
			}
			while (H.size() >= 2 && check(H[H.size() - 2], H.back(), line)) H.pop_back();
			H.emplace_back(line);
		}
	}

	inline pair<T, int> getY(const P &a, const T &x) {
		return make_pair(a.m*x + a.b, a.idx);
	}

	pair<T, int> query(T x) {
		assert(!empty());
		int l = -1, r = H.size() - 1;
		while (l + 1 < r) {
			int m = (l + r) >> 1;
			if (getY(H[m], x) >= getY(H[m + 1], x)) l = m;
			else r = m;
		}
		if (isMin) return getY(H[r], x);
		return make_pair(-getY(H[r], x).first, H[r].idx);
	}

	pair<T, int> queryMonotoneInc(T x) {
		assert(!empty());
		while (H.size() >= 2 && getY(H.front(), x) >= getY(H[1], x)) H.pop_front();
		if (isMin) return getY(H.front(), x);
		return make_pair(-getY(H.front(), x).first, H.front().idx);
	}

	pair<T, int> queryMonotoneDec(T x) {
		assert(!empty());
		while (H.size() >= 2 && getY(H.back(), x) >= getY(H[H.size() - 2], x)) H.pop_back();
		if (isMin) return getY(H.back(), x);
		return make_pair(-getY(H.back(), x).first, H.back().idx);
	}
};
vector<int> solve(int N, const vector<int> &A) {

	ConvexHullTrickWithIndex<int, true> cht;
	vector<vector<pair<int, int> > > X(N);
	vector<vector<pair<int, int> > > Y(N);
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cht.addLine(-2 * (i - 1), -sum + (i - 1) * (i - 1), i);
		pair<int, int> p = cht.queryMonotoneInc(i);
		sum += A[i];
		p.first += i * i + sum;
		//cerr << p.first << " " << p.second << endl;
		X[p.second].push_back(make_pair(p.first, i));
		Y[i].push_back(make_pair(p.first, i));
	}
	vector<int> res(N);
	set <pair<int, int> > st;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < X[i].size(); j++) {
			st.insert(X[i][j]);
		}
		res[i] = (*st.begin()).first;
		for (int j = 0; j < Y[i].size(); j++) {
			st.erase(Y[i][j]);
		}

	}
	return res;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	vector<int> res = solve(N, A);
	reverse(A.begin(), A.end());
	vector<int> res2 = solve(N, A);
	reverse(res2.begin(), res2.end());
	for (int i = 0; i < N; i++) {
		res[i] = min(res[i], res2[i]);
	}
	for (int i = 0; i < N; i++) {
		cout << res[i] << endl;
	}
}
0