#391703 (C++17) No.913 木の燃やし方

提出ソース

結果

問題	No.913 木の燃やし方
ユーザー	はまやんはまやん
提出日時	2019-10-19 11:31:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	855 ms / 3,000 ms
コード長	6,318 bytes
コンパイル時間	2,174 ms
コンパイル使用メモリ	211,180 KB
実行使用メモリ	16,768 KB
最終ジャッジ日時	2024-06-26 23:09:43
合計ジャッジ時間	29,205 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	8 ms 6,940 KB
testcase_04	AC	8 ms 6,940 KB
testcase_05	AC	9 ms 6,940 KB
testcase_06	AC	6 ms 6,944 KB
testcase_07	AC	4 ms 6,944 KB
testcase_08	AC	715 ms 8,832 KB
testcase_09	AC	684 ms 8,576 KB
testcase_10	AC	690 ms 8,576 KB
testcase_11	AC	707 ms 8,680 KB
testcase_12	AC	740 ms 8,960 KB
testcase_13	AC	711 ms 8,704 KB
testcase_14	AC	685 ms 8,576 KB
testcase_15	AC	677 ms 8,576 KB
testcase_16	AC	706 ms 8,832 KB
testcase_17	AC	677 ms 8,576 KB
testcase_18	AC	673 ms 8,576 KB
testcase_19	AC	811 ms 16,768 KB
testcase_20	AC	729 ms 8,832 KB
testcase_21	AC	737 ms 8,960 KB
testcase_22	AC	751 ms 9,216 KB
testcase_23	AC	779 ms 10,240 KB
testcase_24	AC	806 ms 13,184 KB
testcase_25	AC	789 ms 16,640 KB
testcase_26	AC	730 ms 8,832 KB
testcase_27	AC	855 ms 16,768 KB
testcase_28	AC	754 ms 8,960 KB
testcase_29	AC	734 ms 8,832 KB
testcase_30	AC	739 ms 8,960 KB
testcase_31	AC	668 ms 16,768 KB
testcase_32	AC	681 ms 16,768 KB
testcase_33	AC	678 ms 16,740 KB
testcase_34	AC	730 ms 8,832 KB
testcase_35	AC	729 ms 8,832 KB
testcase_36	AC	742 ms 9,088 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function 'bool ConvexHullDynamic::Line::operator<(const ConvexHullDynamic::Line&) const':
main.cpp:50:17: warning: control reaches end of non-void function [-Wreturn-type]
   50 |                 }
      |                 ^

ソースコード

raw source code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
class ConvexHullDynamic
{
	typedef long long coef_t;
	typedef long long coord_t;
	typedef long long val_t;

	/*
	* Line 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
	* and 'xLeft' which is intersection with previous line in hull(first line has -INF)
	*/
private:
	struct Line
	{
		coef_t a, b;
		double xLeft;

		enum Type
		{
			line, maxQuery, minQuery
		} type;
		coord_t val;

		explicit Line(coef_t aa = 0, coef_t bb = 0) : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {}

		val_t valueAt(coord_t x) const { return a * x + b; }

		friend bool areParallel(const Line& l1, const Line& l2) { return l1.a == l2.a; }

		friend double intersectX(const Line& l1, const Line& l2) { return areParallel(l1, l2) ? INFINITY : 1.0 * (l2.b - l1.b) / (l1.a - l2.a); }

		bool operator<(const Line& l2) const
		{
			if (l2.type == line)
				return this->a < l2.a;
			if (l2.type == maxQuery)
				return this->xLeft < l2.val;
			if (l2.type == minQuery)
				return this->xLeft > l2.val;
		}
	};


	bool isMax; //whether or not saved envelope is top(search of max value)
public:
	std::set< Line > hull;  //envelope itself

private:
	/*
	* INFO:        Check position in hull by iterator
	* COMPLEXITY:  O(1)
	*/
	bool hasPrev(std::set< Line >::iterator it) { return it != hull.begin(); }

	bool hasNext(std::set< Line >::iterator it) { return it != hull.end() && std::next(it) != hull.end(); }

	/*
	* INFO:        Check whether line l2 is irrelevant
	* NOTE:        Following positioning in hull must be true
	*              l1 is next left to l2
	*              l2 is right between l1 and l3
	*              l3 is next right to l2
	* COMPLEXITY:  O(1)
	*/
	bool irrelevant(const Line& l1, const Line& l2, const Line& l3) { return intersectX(l1, l3) <= intersectX(l1, l2); }

	bool irrelevant(std::set< Line >::iterator it)
	{
		return hasPrev(it) && hasNext(it)
			&& (isMax && irrelevant(*std::prev(it), *it, *std::next(it))
				|| !isMax && irrelevant(*std::next(it), *it, *std::prev(it)));
	}

	/*
	* INFO:        Updates 'xValue' of line pointed by iterator 'it'
	* COMPLEXITY:  O(1)
	*/
	std::set< Line >::iterator updateLeftBorder(std::set< Line >::iterator it)
	{
		if (isMax && !hasPrev(it) || !isMax && !hasNext(it))
			return it;

		double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it));
		Line buf(*it);
		it = hull.erase(it);
		buf.xLeft = val;
		it = hull.insert(it, buf);
		return it;
	}

public:
	explicit ConvexHullDynamic(bool isMax = false) : isMax(isMax) {}

	/*
	* INFO:        Adding line to the envelope
	*              Line is of type 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
	* COMPLEXITY:  Adding N lines(N calls of function) takes O(N*log N) time
	*/
	void addLine(coef_t a, coef_t b)
	{
		//find the place where line will be inserted in set
		Line l3 = Line(a, b);
		auto it = hull.lower_bound(l3);

		//if parallel line is already in set, one of them becomes irrelevant
		if (it != hull.end() && areParallel(*it, l3)) {
			if (isMax && it->b < b || !isMax && it->b > b)
				it = hull.erase(it);
			else
				return;
		}

		//try to insert
		it = hull.insert(it, l3);
		if (irrelevant(it)) {
			hull.erase(it);
			return;
		}

		//remove lines which became irrelevant after inserting line
		while (hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it));
		while (hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it));

		//refresh 'xLine'
		it = updateLeftBorder(it);
		if (hasPrev(it))
			updateLeftBorder(std::prev(it));
		if (hasNext(it))
			updateLeftBorder(std::next(it));
	}

	val_t getBest(coord_t x) const
	{
		Line q;
		q.val = x;
		q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery;

		auto bestLine = hull.lower_bound(q);
		if (isMax) --bestLine;
		return bestLine->valueAt(x);
	}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, A[201010];
ll B[201010];
//---------------------------------------------------------------------------------------------------
void f(int L, int R, vector<ll>& ans, bool isRev = false) {
	if (L + 1 == R) {
		chmin(ans[L], 1LL + A[L]);
		return;
	}

	int md = (L + R) / 2;
	if (isRev and (R - L) % 2 == 1) md++;
	f(L, md, ans, isRev);
	f(md, R, ans, isRev);

	ConvexHullDynamic cht;
	rep(i, md, R) cht.addLine(-2LL * (i + 1), 1LL * (i + 1) * (i + 1) + B[i]);
	
	ll mi = infl;
	rep(i, L, md) {
		ll cst = cht.getBest(i) + 1LL * i * i;
		if (i) cst -= B[i - 1];
		chmin(mi, cst);
		chmin(ans[i], mi);
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];

	vector<ll> normal(N, infl);
	B[0] = A[0];
	rep(i, 1, N) B[i] = B[i - 1] + A[i];
	f(0, N, normal);

	reverse(A, A + N);

	vector<ll> rev(N, infl);
	B[0] = A[0];
	rep(i, 1, N) B[i] = B[i - 1] + A[i];
	f(0, N, rev, true);

	rep(i, 0, N) printf("%lld\n", min(normal[i], rev[N - 1 - i]));
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード