#1198105 (C++23) No.2078 魔抜けなパープル

• 問題: No.2078 魔抜けなパープル
• ユーザー: drken1215
• 提出日時: 2026-11-11 12:59:03
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 624 ms / 2,000 ms
• コード長: 16,511 bytes
• コンパイル時間: 2,452 ms
• コンパイル使用メモリ: 351,300 KB
• 実行使用メモリ: 11,776 KB
• 最終ジャッジ日時: 2026-11-11 12:59:10
• 合計ジャッジ時間: 6,415 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 7

ソースコード

#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/409"

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

#line 4 "https://drken1215.github.io/algorithm/template.hpp.html"
using namespace std;

// My library is in https://github.com/drken1215/algorithm
#line 4 "https://drken1215.github.io/algorithm/Others/macro.hpp.html"
using namespace std;

using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#line 3 "https://drken1215.github.io/algorithm/Others/stl_container_stream.hpp.html"
using namespace std;

// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }

// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }

// Yes/No
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
#line 4 "https://drken1215.github.io/algorithm/Optimization/monge_shortest_path_by_cht.hpp.html"
using namespace std;

#line 4 "https://drken1215.github.io/algorithm/Optimization/general_li_chao_tree.hpp.html"
using namespace std;

// General Li-Chao Tree (Dynamic ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    struct Node {
        int id = -1;  // function id
        Node *left = nullptr, *right = nullptr;
    };
    
    // inner values using chunk-based memory pool
    vector<unique_ptr<Node[]>> blocks;
    vector<FUNC> funcs;
    Node *root = nullptr;
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    
    // constructors
    explicit DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2)
    : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        blocks.clear();
        used = BLOCK;
        root = nullptr;
    }

    // insert(f), in O(log X)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        insert_at(root, XL, XR, id);
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    int insert_segment(FUNC f, X l, X r) {
        assert(XL <= l && l <= r && r <= XR);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (l != r) insert_segment_at(root, XL, XR, l, r, id);
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        VAL best = INF;
        int best_id = -1;
        Node *p = root;
        X left = XL, right = XR;
        while (p) {
            if (p->id != -1) {
                int fid = p->id;
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) p = p->left, right = mid;
            else p = p->right, left = mid;
        }
        return {best, best_id};
    }

private:
    // chunk-based node allocation
    static constexpr int BLOCK = 4096;
    int used = BLOCK;
    Node *new_node() {
        if (used == BLOCK) {
            blocks.emplace_back(make_unique<Node[]>(BLOCK));
            used = 0;
        }
        return &blocks.back()[used++];
    }

    // inner insert
    void insert_at(Node *&p, X left, X right, int fid) {
        Node **cur = &p;
        while (true) {
            if (!*cur) *cur = new_node();
            Node *v = *cur;
            int gid = v->id;
            if (gid == -1) {
                v->id = fid;
                return;
            }
            bool left_better = better(fid, gid, left), right_better = better(fid, gid, right - 1);
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                v->id = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, mid);
            if (mid_better) v->id = fid, fid = gid;
            if (left_better != mid_better) cur = &v->left, right = mid;
            else cur = &v->right, left = mid;
        }
    }

    // inner insert_segment
    void insert_segment_at(Node *&p, X left, X right, X l, X r, int fid) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert_at(p, left, right, fid);
            return;
        }
        if (!p) p = new_node();
        X mid = (left + right) / 2;
        if (l < mid) insert_segment_at(p->left, left, mid, l, r, fid);
        if (mid < r) insert_segment_at(p->right, mid, right, l, r, fid);
    }
};

// General Li-Chao Tree (static ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct GeneralLiChaoTree {
    // inner values
    int N, XL, SIZ;
    bool compressed = true;
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<X> xs;
    vector<int> ids;
    vector<FUNC> funcs;

    // constructors
    explicit GeneralLiChaoTree(vector<X> xs_, VAL inf = numeric_limits<VAL>::max() / 2, bool sorted = true) 
    : N((int)xs_.size()), XL(0), SIZ(1), compressed(true), INF(inf), xs(std::move(xs_)) {
        if (!sorted) {
            sort(xs.begin(), xs.end());
            xs.erase(unique(xs.begin(), xs.end()), xs.end());
        }
        while (SIZ < N) SIZ <<= 1;
        ids.assign(SIZ << 1, -1);
    }
    explicit GeneralLiChaoTree(int xl, int xr, VAL inf = numeric_limits<VAL>::max() / 2) 
    : N(xr - xl), XL(xl), SIZ(1), compressed(false), INF(inf) {
        assert(N >= 0);
        while (SIZ < N) SIZ <<= 1;
        ids.assign(SIZ << 1, -1);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        fill(ids.begin(), ids.end(), -1);
    }

    // insert(f), in O(log N)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N) insert_at(1, 0, SIZ, id);
        return id;
    }

    // insert_segment(f, l, r), in O(log^2 N)
    int insert_segment(FUNC f, X l, X r) {
        assert(l <= r);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N == 0 || l == r) return id;
        int L = lower_bound_index(l);
        int R = lower_bound_index(r);
        if (L == R) return id;
        int a = L + SIZ, b = R + SIZ;
        while (a < b) {
            if (a & 1) {
                int v = a++;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = SIZ >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            if (b & 1) {
                int v = --b;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = SIZ >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            a >>= 1, b >>= 1;
        }
        return id;
    }

    // query(x), x must be in xs, in O(log N)
    pair<VAL, int> query(X x) const {
        int pos = 0;
        if (compressed) {
            auto it = lower_bound(xs.begin(), xs.end(), x);
            assert(it != xs.end() && *it == x);
            pos = int(it - xs.begin());
        } else {
            assert(X(XL) <= x && x < X(XL + N));
            pos = int(x - XL);
        }
        VAL best = INF;
        int best_id = -1;
        int v = pos + SIZ;
        while (v) {
            int fid = ids[v];
            if (fid != -1) {
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            v >>= 1;
        }
        return {best, best_id};
    }

private:
    // coordinate compression
    int lower_bound_index(X x) const {
        if (compressed) {
            return int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        } else {
            if (x <= X(XL)) return 0;
            else if (x >= X(XL) + X(N)) return N;
            else return int(x - X(XL));
        }
    }

    // inner insert
    void insert_at(int v, int left, int right, int fid) {
        auto coord = [&](int i) -> X { 
            i = min(i, N - 1);
            return (compressed ? xs[i] : X(i) + X(XL));
        };
        while (true) {
            int gid = ids[v];
            if (gid == -1) {
                ids[v] = fid;
                return;
            }
            bool left_better = better(fid, gid, coord(left));
            bool right_better = better(fid, gid, coord(right - 1));
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                ids[v] = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, coord(mid));
            if (mid_better) ids[v] = fid, fid = gid;
            if (left_better != mid_better) {
                v <<= 1;
                right = mid;
            } else {
                v = v << 1 | 1;
                left = mid;
            }
        }
    }
};
#line 7 "https://drken1215.github.io/algorithm/Optimization/monge_shortest_path_by_cht.hpp.html"

// find shortest path on DAG with Pairwise Single Crossing cost, by Li Chao Tree, O(N log N)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be Pairwise Single Crossing (must be in all 0 <= i, j <= N, including i >= j)
// Attention: Even if f is Pairwise Single Crossing, A is not necessarily Pairwise Single Crossing
// edges: (i, j), j >= start[i] (i + 1 <= start[i] <= N + 1), start is non-decreasing
template<class VAL, class FUNC> vector<pair<VAL, int>> MongeShortestPathByCHT
(int N, const FUNC &f, const vector<int> &start, bool use_segment_insertion = true) {
    assert((int)start.size() == N);
    for (int i = 0; i < N; i++) {
        assert(i + 1 <= start[i] && start[i] <= N + 1);
        if (i > 0) assert(start[i - 1] <= start[i]);
    }
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<pair<VAL, int>> dp(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
    auto make_func = [&](int i) {
        return [&, i](long long j) -> VAL { return dp[i].first + f(i, j); };
    };
    GeneralLiChaoTree<VAL, decltype(make_func(0))> cht(1, N + 1, INF);
    dp[0].first = 0;
    int i = 0;
    for (int j = 1; j <= N; j++) {
        while (i < N && j >= start[i]) {
            if (use_segment_insertion) {
                // 挿入する関数群が j >= start[i] の領域でのみ PSC であるとき、use_segment_insertion = true にする
                cht.insert_segment(make_func(i), start[i], N + 1);
            } else {
                // 挿入する関数群が全ての i, j に対して PSC であるとき、use_segment_insertion = false にする
                cht.insert(make_func(i));
            }
            i++;
        }
        dp[j] = cht.query(j);
    };
    return dp;
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MongeShortestPathByCHT
(int N, const FUNC &f, bool use_segment_insertion = true) {
    vector<int> start(N);
    for (int i = 0; i < N; i++) start[i] = i + 1;
    return MongeShortestPathByCHT<VAL>(N, f, start, use_segment_insertion);
}
#line 8 "test.cpp"

/*
    dp[j] = min_{j < i} (dp[i] + func(i, j))
    func(i, j) = (j - i)^2 + X
*/
void solve() {
    ll X, A;
    cin >> X >> A;
    auto func = [&](ll i, ll j) -> ll { return (j - i) * (j - i) + X; };
    auto res = MongeShortestPathByCHT<ll>(A, func);
    cout << res.back().first << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}