結果
問題 | No.913 木の燃やし方 |
ユーザー |
👑 ![]() |
提出日時 | 2019-11-26 18:28:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 3,000 ms |
コード長 | 4,862 bytes |
コンパイル時間 | 2,871 ms |
コンパイル使用メモリ | 128,584 KB |
最終ジャッジ日時 | 2025-01-08 05:39:44 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <chrono>#define _USE_MATH_DEFINES#include <cmath>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <iomanip>#include <iterator>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <utility>#include <vector>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()const int INF = 0x3f3f3f3f;const long long LINF = 0x3f3f3f3f3f3f3f3fLL;const double EPS = 1e-8;const int MOD = 1000000007;// const int MOD = 998244353;const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},// dx[] = {0, -1, -1, -1, 0, 1, 1, 1};struct IOSetup {IOSetup() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(20);cerr << fixed << setprecision(10);}} iosetup;/*-------------------------------------------------*/template <typename T>struct CHT {using Line = pair<T, T>;CHT(bool is_minimized = true) : is_minimized(is_minimized) {}void add(T a, T b) {Line now(a, b);if (deq.empty()) {deq.emplace_back(now);} else if (deq.back().first <= a) {if (deq.back().first == a) {if (is_minimized) {if (b >= deq.back().second) return;deq.pop_back();} else {if (b <= deq.back().second) return;deq.pop_back();}}while (deq.size() >= 2 && !is_necessary(deq[deq.size() - 2], deq.back(), now)) deq.pop_back();deq.emplace_back(now);} else {if (deq.front().first == a) {if (is_minimized) {if (b >= deq.front().second) return;deq.pop_front();} else {if (b <= deq.front().second) return;deq.pop_front();}}while (deq.size() >= 2 && !is_necessary(now, deq[0], deq[1])) deq.pop_front();deq.emplace_front(now);}}T query(T x) {int lb = -1, ub = deq.size() - 1;while (ub - lb > 1) {int mid = (lb + ub) >> 1;if (is_minimized) {(f(deq[mid], x) < f(deq[mid + 1], x) ? ub : lb) = mid;} else {(f(deq[mid], x) > f(deq[mid + 1], x) ? ub : lb) = mid;}}return f(deq[ub], x);}T monotone_inc_query(T x) {if (is_minimized) {while (deq.size() >= 2 && f(deq[deq.size() - 2], x) <= f(deq.back(), x)) deq.pop_back();return f(deq.back(), x);} else {while (deq.size() >= 2 && f(deq[0], x) <= f(deq[1], x)) deq.pop_front();return f(deq.front(), x);}}T monotone_dec_query(T x) {if (is_minimized) {while (deq.size() >= 2 && f(deq[0], x) >= f(deq[1], x)) deq.pop_front();return f(deq.front(), x);} else {while (deq.size() >= 2 && f(deq[deq.size() - 2], x) >= f(deq.back(), x)) deq.pop_back();return f(deq.back(), x);}}private:bool is_minimized;deque<Line> deq;using Real = long double;bool is_necessary(const Line &l1, const Line &l2, const Line &l3) {Real lhs = static_cast<Real>(l3.second - l2.second) / (l2.first - l3.first);Real rhs = static_cast<Real>(l2.second - l1.second) / (l1.first - l2.first);// T lhs = (l1.first - l2.first) * (l3.second - l2.second);// T rhs = (l2.first - l3.first) * (l2.second - l1.second);return is_minimized ? lhs < rhs : lhs > rhs;}T f(const Line &l, T x) { return l.first * x + l.second; }};int main() {int n; cin >> n;vector<long long> a(n); REP(i, n) cin >> a[i];FOR(i, 1, n) a[i] += a[i - 1];vector<long long> ans(n, LINF);function<void(int, int)> rec = [&](int l, int r) {if (r <= l) return;if (l + 1 == r) {ans[l] = min(ans[l], a[l] - (l > 0 ? a[l - 1] : 0) + 1);return;}int mid = (l + r) / 2;rec(l, mid);rec(mid, r);CHT<long long> cht1;FOR(i, mid, r) cht1.add(-2 * i, 1LL * i * i + 2 * i + a[i]);vector<long long> memo1(mid - l);FOR(i, l, mid) memo1[i - l] = cht1.monotone_inc_query(i) + 1LL * i * i - 2 * i - (i > 0 ? a[i - 1] : 0) + 1;FOR(i, 1, mid - l) memo1[i] = min(memo1[i], memo1[i - 1]);FOR(i, l, mid) ans[i] = min(ans[i], memo1[i - l]);CHT<long long> cht2;FOR(i, l, mid + 1) cht2.add(-2 * i, 1LL * i * i - 2 * i - (i > 0 ? a[i - 1] : 0));vector<long long> memo2(r - mid);FOR(i, mid, r) memo2[i - mid] = cht2.monotone_inc_query(i) + 1LL * i * i + 2 * i + a[i] + 1;for (int i = r - mid - 2; i >= 0; --i) memo2[i] = min(memo2[i], memo2[i + 1]);FOR(i, mid, r) ans[i] = min(ans[i], memo2[i - mid]);};rec(0, n);REP(i, n) cout << ans[i] << '\n';return 0;}