結果

問題 No.703 ゴミ拾い Easy
ユーザー kcvlexkcvlex
提出日時 2019-06-05 21:16:33
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,371 bytes
コンパイル時間 1,321 ms
コンパイル使用メモリ 145,412 KB
最終ジャッジ日時 2023-08-30 19:05:50
合計ジャッジ時間 3,361 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:46:43: error: ‘make_v’ function uses ‘auto’ type specifier without trailing return type
 auto make_v(T init, size_t s, Tail... tail) {
                                           ^
main.cpp:46:43: note: deduced return type only available with -std=c++14 or -std=gnu++14

ソースコード

diff # 

// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

class LiChaoTree {
    using Line = PLL;
    V<ll> x_coors;
    V<Line> nodes;
    ll node_begin_idx;
    function<ll(ll, ll)> comp;    // maybe min or max
    function<bool(ll, ll)> comp_bool;
    Line invalid;
    ll inf, identity_ele;

    ll get_x_coor(ll xidx) { return xidx < x_coors.size() ? x_coors[xidx] : inf; }

    void add_line_(Line line, ll node_idx, ll lidx, ll ridx) {
        if(nodes.size() <= node_idx) return;
        if(nodes[node_idx] == invalid) {
            nodes[node_idx] = line;
            return;
        }

        ll midx = (lidx + ridx) / 2;
        ll lx = get_x_coor(lidx);
        ll mx = get_x_coor(midx);
        ll rx = get_x_coor(ridx);
        
        if(lx == inf) return;
        
        bool left_comp  = comp_bool(calc_y(line, lx), calc_y(nodes[node_idx], lx));
        bool mid_comp   = comp_bool(calc_y(line, mx), calc_y(nodes[node_idx], mx));
        bool right_comp = comp_bool(calc_y(line, rx), calc_y(nodes[node_idx], rx));

        if(left_comp && right_comp) {
            nodes[node_idx] = line;
            return;
        }
        if(!left_comp && !right_comp) return;
        if(mid_comp) {
            swap(line, nodes[node_idx]);
            left_comp = !left_comp;
            right_comp = !right_comp;
        }
        if(left_comp) add_line_(line, 2 * node_idx + 1, lidx, midx);
        else          add_line_(line, 2 * node_idx + 2, midx, ridx);
    }

public:

    LiChaoTree(const V<ll> &x_coors, function<ll(ll, ll)> comp, 
               ll identity_ele, ll inf, Line invalid = Line(1e9, 1e9))
        : comp(comp),
          comp_bool([this](ll a, ll b) { return this->comp(a, b) == a; }),
          identity_ele(identity_ele),
          inf(inf),
          invalid(invalid)
    {
        ll tmp = 1;
        while(tmp < x_coors.size()) tmp *= 2;
        node_begin_idx = tmp - 1;
        this->x_coors.resize(tmp);
        nodes.resize(2 * tmp - 1, invalid);
        for(ll i = 0; i < x_coors.size(); i++) this->x_coors[i] = x_coors[i];
        for(ll i = x_coors.size(); i < tmp; i++) this->x_coors[i] = inf;
    }

    ll calc_y(Line line, ll x) {
        if(line == invalid) return identity_ele;
        ll a, b;
        tie(a, b) = line;
        return a * x + b;
    }

    ll calc_y(ll idx, ll x) { return calc_y(nodes[idx], x); }
    
    void add_line(Line line) { add_line_(line, 0, 0, x_coors.size()); }
    void add_line(ll x, ll y) { add_line(Line(x, y)); }

    ll query(ll xidx) {
        ll node_idx = xidx + node_begin_idx;
        ll x = x_coors[xidx];
        ll ret = identity_ele;
        while(true) {
            if(nodes[node_idx] != invalid) {
                ll y = calc_y(node_idx, x);
                ret = comp(ret, y);
            }
            if(!node_idx) break;
            node_idx = (node_idx - 1) / 2;
        }
        return ret;
    }
};

inline void input(V<ll> &v) { for(ll &e : v) cin >> e; }
const ll inf = 1e12;
const PLL invalid = make_pair(inf, inf);

PLL create_line(ll x, ll y, ll val) {
    if(x == inf || y == inf || val == inf) return invalid;
    return make_pair(-2 * x, x * x + y * y + val);
}

int main() {
    ll N;
    cin >> N;

    V<ll> A(N), X(N), Y(N);
    input(A);
    input(X);
    input(Y);
    X.push_back(inf);
    Y.push_back(inf);

    LiChaoTree lct(A, [](ll a, ll b) { return min(a, b); }, inf, inf, invalid);
    lct.add_line(create_line(X[0], Y[0], 0));

    ll ans = pow(X[0] - A[0], 2) + pow(Y[0], 2);

    for(ll i = 0; i < N; i++) {
        ll val = lct.query(i);
        val += A[i] * A[i];
        ans = val;
        DEBUG(val);
        lct.add_line(create_line(X[i + 1], Y[i + 1], val));
    }

    cout << ans << endl;
    return 0;
}
0