結果

問題 No.913 木の燃やし方
ユーザー ats5515ats5515
提出日時 2019-10-18 21:55:36
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,575 bytes
コンパイル時間 1,309 ms
コンパイル使用メモリ 98,736 KB
実行使用メモリ 43,980 KB
最終ジャッジ日時 2023-09-07 22:21:15
合計ジャッジ時間 17,827 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 8 ms
4,380 KB
testcase_06 WA -
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 468 ms
35,724 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 504 ms
36,828 KB
testcase_13 AC 459 ms
37,852 KB
testcase_14 AC 453 ms
36,336 KB
testcase_15 AC 459 ms
36,424 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 372 ms
29,836 KB
testcase_20 AC 376 ms
29,632 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 361 ms
28,900 KB
testcase_25 AC 345 ms
29,552 KB
testcase_26 AC 502 ms
39,140 KB
testcase_27 AC 504 ms
43,980 KB
testcase_28 AC 424 ms
38,952 KB
testcase_29 AC 450 ms
38,900 KB
testcase_30 AC 430 ms
31,976 KB
testcase_31 AC 451 ms
40,836 KB
testcase_32 AC 457 ms
42,688 KB
testcase_33 AC 470 ms
42,284 KB
testcase_34 AC 429 ms
35,364 KB
testcase_35 AC 433 ms
35,276 KB
testcase_36 AC 374 ms
31,124 KB
権限があれば一括ダウンロードができます

ソースコード

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