結果
| 問題 |
No.913 木の燃やし方
|
| コンテスト | |
| ユーザー |
 AC2K
|
| 提出日時 | 2024-08-07 15:14:45 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,262 bytes |
| コンパイル時間 | 3,250 ms |
| コンパイル使用メモリ | 257,756 KB |
| 実行使用メモリ | 14,108 KB |
| 最終ジャッジ日時 | 2024-08-07 15:14:56 |
| 合計ジャッジ時間 | 10,657 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 TLE * 1 -- * 28 |
ソースコード
#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif
/**
* @brief Debugger
*/
#line 2 "Library/src/data-structure/CHT.hpp"
#include <set>
namespace kyopro {
/**
* @tparam query_type trueにすると, クエリで最大値を求めるように変更する
*/
template <class T = long long, bool query_type = false> class CHT {
class line {
public:
T a, b;
bool is_query;
mutable T nxt_a, nxt_b;
mutable bool has_nxt;
T get(T x) const { return a * x + b; }
T get_nxt(T x) const { return nxt_a * x + nxt_b; }
line(T a, T b, bool q = false)
: a(a), b(b), is_query(q), has_nxt(false) {}
friend bool operator<(const line& l, const line& r) {
if (l.is_query) {
if (!r.has_nxt) return true;
return r.get(l.a) < r.get_nxt(l.a);
}
if (r.is_query) {
if (!l.has_nxt) return false;
return l.get(r.a) > l.get_nxt(r.a);
}
return l.a == r.a ? l.b < r.b : l.a < r.a;
}
};
std::set<line> ls;
bool is_needed(const typename std::set<line>::iterator& it) {
if (it != ls.begin() && it->a == prev(it)->a) {
return it->b < prev(it)->b;
}
if (next(it) != ls.end() && it->a == next(it)->a) {
return it->b < next(it)->b;
}
if (it == ls.begin() || next(it) == ls.end()) {
return true;
}
return 1. * (it->b - prev(it)->b) * (next(it)->a - it->a) <
1. * (it->b - next(it)->b) * (prev(it)->a - it->a);
}
public:
void insert(T a, T b) {
if (query_type) {
ls.emplace(-a, -b);
} else {
ls.emplace(a, b);
}
const line& ln = (query_type ? line{-a, -b} : line{a, b});
auto it = ls.find(ln);
if (!is_needed(it)) {
ls.erase(it);
return;
}
while (it != ls.begin() && !is_needed(prev(it))) {
ls.erase(prev(it));
}
while (next(it) != ls.end() && !is_needed(next(it))) {
ls.erase(next(it));
}
if (it != ls.begin()) {
prev(it)->has_nxt = true;
prev(it)->nxt_a = it->a;
prev(it)->nxt_b = it->b;
}
if (next(it) != ls.end()) {
it->has_nxt = true;
it->nxt_a = next(it)->a;
it->nxt_b = next(it)->b;
}
}
T operator()(T x) const {
const auto& it = ls.lower_bound(line(x, 0, true));
if (query_type) {
return -it->a * x - it->b;
} else {
return it->a * x + it->b;
}
}
};
}; // namespace kyopro
/**
* @brief Convex Hull Trick
*/
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "Library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
#include <cstdint>
namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
: first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
using type = T;
};
template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
std::enable_if<dgt <= 16, std::int16_t>,
std::enable_if<dgt <= 32, std::int32_t>,
std::enable_if<dgt <= 64, std::int64_t>,
std::enable_if<dgt <= 128, __int128_t>>;
};
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
std::enable_if<dgt <= 16, std::uint16_t>,
std::enable_if<dgt <= 32, std::uint32_t>,
std::enable_if<dgt <= 64, std::uint64_t>,
std::enable_if<dgt <= 128, __uint128_t>>;
};
template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;
template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;
template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
// is_integral
template <typename T>
using is_integral_t =
std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
std::is_same_v<T, __uint128_t>>;
}; // namespace internal
}; // namespace kyopro
/**
* @brief Type Traits
* @see https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
*/
#line 6 "Library/src/stream.hpp"
namespace kyopro {
inline void single_read(char& c) {
c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
a = 0;
bool is_negative = false;
char c = getchar_unlocked();
while (isspace(c)) {
c = getchar_unlocked();
}
if (c == '-') is_negative = true, c = getchar_unlocked();
while (isdigit(c)) {
a = 10 * a + (c - '0');
c = getchar_unlocked();
}
if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
long long x;
single_read(x);
a = T(x);
}
inline void single_read(std::string& str) noexcept {
char c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
while (!isspace(c)) {
str += c;
c = getchar_unlocked();
}
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
single_read(head), read(tail...);
}
inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
if (!a) {
putchar_unlocked('0');
return;
}
if constexpr (std::is_signed_v<T>) {
if (a < 0) putchar_unlocked('-'), a *= -1;
}
constexpr int d = std::numeric_limits<T>::digits10;
char s[d + 1];
int now = d + 1;
while (a) {
s[--now] = (char)'0' + a % 10;
a /= 10;
}
while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
for (auto c : str) {
putchar_unlocked(c);
}
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
single_write(head);
putchar_unlocked(' ');
write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
write(x...);
putchar_unlocked('\n');
}
}; // namespace kyopro
/**
* @brief Fast IO(高速入出力)
*/
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
return a > b && (a = b, true);
}
/**
* @brief Template
*/
#line 5 "a.cpp"
using namespace std;
using namespace kyopro;
int main() {
int n;
read(n);
vector a(n, 0);
rep(i, n) read(a[i]);
vector sa(n + 1, 0LL);
rep(i, n) sa[i + 1] = sa[i] + a[i];
vector answer(n, infl);
// calc for all i \in [l,r)
auto f = [&](const auto& f, int l, int r) -> void {
if (l == r) return;
if (r - l == 1) {
chmin(answer[l], 1 + a[l]);
return;
}
int m = (l + r) / 2;
// mを燃やす?
// mを燃やさない(mをまたがない)なら下に潜る
f(f, l, m);
f(f, m, r);
// 燃やすなら...
{
CHT<ll> cht;
for (int i = m + 1; i <= r; ++i) {
cht.insert(-2 * i, ll(i) * i + sa[i]);
}
ll pref_min = infl;
for (int i = 0; i <= m; ++i) {
chmin(pref_min, ll(i) * i - sa[i] + cht(i));
chmin(answer[i], pref_min);
}
}
{
CHT<ll> cht;
for (int i = l; i <= m; ++i) {
// debug(i);
// debug(2 * i);
// debug(i * i - sa[i]);
cht.insert(-2 * i, (ll)i * i - sa[i]);
}
ll suff_min = infl;
for (int i = r - 1; i > m; --i) {
// debug(suff_min);
chmin(answer[i], suff_min);
chmin(suff_min, ll(i) * i + sa[i] + cht(i));
}
}
};
f(f, 0, n);
rep(i, n) put(answer[i]);
}