結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2019-06-05 21:16:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,371 bytes |
コンパイル時間 | 1,296 ms |
コンパイル使用メモリ | 162,788 KB |
最終ジャッジ日時 | 2024-11-14 21:28:01 |
合計ジャッジ時間 | 2,972 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:46:1: error: ‘make_v’ function uses ‘auto’ type specifier without trailing return type 46 | auto make_v(T init, size_t s, Tail... tail) { | ^~~~ main.cpp:46:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
ソースコード
// #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; }