結果

問題 No.913 木の燃やし方
ユーザー noiminoimi
提出日時 2024-08-16 17:50:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 215 ms / 3,000 ms
コード長 5,563 bytes
コンパイル時間 3,683 ms
コンパイル使用メモリ 232,904 KB
実行使用メモリ 14,224 KB
最終ジャッジ日時 2024-08-16 17:50:54
合計ジャッジ時間 14,227 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 4 ms
6,940 KB
testcase_05 AC 4 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,948 KB
testcase_08 AC 205 ms
13,696 KB
testcase_09 AC 210 ms
13,440 KB
testcase_10 AC 201 ms
13,220 KB
testcase_11 AC 204 ms
13,584 KB
testcase_12 AC 215 ms
14,080 KB
testcase_13 AC 194 ms
13,696 KB
testcase_14 AC 185 ms
13,440 KB
testcase_15 AC 194 ms
13,224 KB
testcase_16 AC 188 ms
13,824 KB
testcase_17 AC 184 ms
13,312 KB
testcase_18 AC 178 ms
13,224 KB
testcase_19 AC 194 ms
14,068 KB
testcase_20 AC 196 ms
14,080 KB
testcase_21 AC 209 ms
14,192 KB
testcase_22 AC 190 ms
14,176 KB
testcase_23 AC 171 ms
14,048 KB
testcase_24 AC 147 ms
14,176 KB
testcase_25 AC 141 ms
14,224 KB
testcase_26 AC 199 ms
14,096 KB
testcase_27 AC 215 ms
14,208 KB
testcase_28 AC 204 ms
14,080 KB
testcase_29 AC 193 ms
14,156 KB
testcase_30 AC 197 ms
14,208 KB
testcase_31 AC 185 ms
14,208 KB
testcase_32 AC 184 ms
14,068 KB
testcase_33 AC 195 ms
14,196 KB
testcase_34 AC 177 ms
14,052 KB
testcase_35 AC 167 ms
14,068 KB
testcase_36 AC 161 ms
14,196 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:20:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   20 | bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
      |            ^~~~
main.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   20 | bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
      |                     ^~~~
main.cpp:21:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   21 | bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
      |            ^~~~
main.cpp:21:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   21 | bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
      |                     ^~~~

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov3(a, b, c, name, ...) name
#define rep0(n) for(ll aaaaa = 0; aaaaa < (n); aaaaa++)
#define rep1(i, n) for(ll i = 0; i < (n); i++)
#define rep2(i, a, b) for(ll i = (a); i < (b); i++)
#define rep(...) ov3(__VA_ARGS__, rep2, rep1, rep0)(__VA_ARGS__)
#define fore(e, v) for(auto &&e : v)
#define all(v) begin(v), end(v)
#define si(a) (int)(size(a))
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
const int inf = 11e8;
const ll infl = 2e18;

#define i128 __int128_t

template <bool isMin = true> struct CHT {
#define x first
#define y second
    CHT() = default;
    deque<pll> v;
    bool empty() { return v.empty(); }
    void clear() { return v.clear(); }
    inline int sgn(ll x) { return !x ? 0 : (x < 0 ? -1 : 1); }
    using D = long double;
    inline bool check(const pll &a, const pll &b, const pll &c) {
        if(b.y == a.y or c.y == b.y) return sgn(b.x - a.x) * sgn(c.y - b.y) >= sgn(c.x - b.x) * sgn(b.y - a.y);
        return D(b.x - a.x) * sgn(c.y - b.y) / D(abs(b.y - a.y)) >= D(c.x - b.x) * sgn(b.y - a.y) / D(abs(c.y - b.y));
    }
    void add(ll a, ll b) {
        if(!isMin) a *= -1, b *= -1;
        pll line(a, b);
        if(empty())
            v.emplace_front(line);
        else {
            if(ll c = v[0].x; c <= a) {
                if(c == a) {
                    if(v[0].y <= b) return;
                    v.pop_front();
                }
                while(si(v) >= 2 and check(line, v[0], v[1])) v.pop_front();
                v.emplace_front(line);
            } else {
                assert(a <= v.back().x);
                if(v.back().x == a) {
                    if(v.back().y <= b) return;
                    v.pop_back();
                }
                while(si(v) >= 2 and check(v[si(v) - 2], v.back(), line)) v.pop_back();
                v.emplace_back(line);
            }
        }
    }
    ll get_y(const pll &a, const ll &x) { return a.x * x + a.y; }
    ll query(ll x) {
        assert(!empty());
        int l = -1, r = si(v) - 1;
        while(l + 1 < r) {
            int m = (l + r) >> 1;
            if(get_y(v[m], x) >= get_y(v[m + 1], x))
                l = m;
            else
                r = m;
        }
        return get_y(v[r], x) * (isMin ? 1 : -1);
    }
    ll query_monotone_inc(ll x) {
        assert(!empty());
        while(si(v) >= 2 and get_y(v[0], x) >= get_y(v[1], x)) v.pop_front();
        return get_y(v[0], x) * (isMin ? 1 : -1);
    }
    ll query_monotone_dec(ll x) {
        assert(!empty());
        while(si(v) >= 2 and get_y(v.back(), x) >= get_y(v.end()[-2], x)) v.pop_back();
        return get_y(v.back(), x) * (isMin ? 1 : -1);
    }
#undef x
#undef y
};

// A[N + 1][N + 1]: Monge が i > j のみ存在しているとき、i (= 0, ..., N)行目の最小値を返す
// f(i, j, v) で、j 行目の最小値が求まっている v を用いて、A[i][j] にアクセス
template <typename T, typename F> vector<T> monge_rowmin(int n, const F &f) {
    vector<T> mi(n + 1, numeric_limits<T>::min());
    vector<int> amin(n + 1);
    auto check = [&](int i, int j) {
        if(chmin(mi[i], f(i, j, mi))) { amin[i] = j; }
    };
    check(n, 0);
    auto solve = [&](auto &&self, int l, int r) {
        if(r - l == 1) return;
        int mid = l + r >> 1;
        rep(k, amin[l], amin[r] + 1) check(mid, k);
        self(self, l, mid);
        rep(k, l + 1, mid + 1) check(r, k);
        self(self, mid, r);
    };
    return mi;
}

// monotone 行列の各行について、最小値を取る場所とその値を返す
template <typename T, typename F> vector<pair<int, T>> monotone_minima(int h, int w, const F &f) {
    vector<pair<int, T>> dp(h, pair(-1, T()));
    auto rec = [&](auto &&rec, int u, int d, int l, int r) {
        if(u > d) return;
        int mid = u + d >> 1;
        auto &[idx, mi] = dp[mid];
        idx = l, mi = f(mid, l);
        rep(i, l + 1, r + 1) if(chmin(mi, f(mid, i))) idx = i;
        rec(rec, u, mid - 1, l, idx);
        rec(rec, mid + 1, d, idx, r);
    };
    rec(rec, 0, h - 1, 0, w - 1);
    return dp;
}

int main() {
    int n;
    cin >> n;
    vl a(n);
    fore(e, a) cin >> e;
    vl c(n + 1);
    rep(i, n) c[i + 1] = c[i] + a[i];
    // (r - l) ^ 2 + c[r] - c[l]
    // (r ^ 2 + c[r]) - (c[l] - l^2) - 2lr

    auto cost = [&](int l, int r) { return (ll)(r - l) * (r - l) + c[r] - c[l]; };

    vl res(n, infl);
    auto rec = [&](auto &&f, int l, int r) {
        if(l + 1 == r) {
            chmin(res[l], 1 + a[l]);
            return;
        }
        int mid = l + r >> 1;
        auto dpl = monotone_minima<ll>(mid - l, r - mid + 1, [&](int i, int j) {
            int L = i + l, R = mid + j;
            return cost(L, R);
        });
        auto dpr = monotone_minima<ll>(r - mid + 1, mid - l, [&](int i, int j) {
            int L = j + l, R = mid + i;
            return cost(L, R);
        });

        ll mi = infl;
        rep(i, mid - l) {
            chmin(mi, dpl[i].second);
            chmin(res[l + i], mi);
        }
        mi = infl;
        for(int i = r; i > mid; i--) {
            chmin(mi, dpr[i - mid].second);
            chmin(res[i - 1], mi);
        }
        f(f, l, mid), f(f, mid, r);
    };
    rec(rec, 0, n);
    rep(i, n) { cout << res[i] << '\n'; }
}
0