結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-21 19:54:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 122 ms / 1,500 ms
コード長 1,916 bytes
コンパイル時間 3,436 ms
コンパイル使用メモリ 276,376 KB
実行使用メモリ 29,440 KB
最終ジャッジ日時 2025-03-21 19:55:08
合計ジャッジ時間 9,180 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
#define int ll
const int INF = 1e18;
const int MAXN = 3e5 + 5;
int n, m, dp[MAXN];
int a[MAXN], x[MAXN], y[MAXN];
struct LCT
{
    struct node
    {
        int k, b;
        node(int _k = 0, int _b = 1e18) : k(_k), b(_b) {}
        int operator()(const int &x) const & { return k * x + b; }
        bool operator==(const node &T) const & { return k == T.k && b == T.b; }
    } tree[MAXN << 2];
    node cmp(node a, node b, int x)
    {
        if (a(x) - b(x) > 0)
            return b;
        if (b(x) - a(x) > 0)
            return a;
        return a;
    }
    void add(int id, int l, int r, node val)
    {
        if (tree[id] == val)
            return;
        if (cmp(tree[id], val, mid) == val)
            swap(tree[id], val);
        if (cmp(tree[id], val, l) == val)
            add(ls, l, mid, val);
        if (cmp(tree[id], val, r) == val)
            add(rs, mid + 1, r, val);
    }
    node query(int id, int l, int r, int x)
    {
        if (l == r)
            return tree[id];
        node a = tree[id], b;
        if (x <= mid)
            b = query(ls, l, mid, x);
        else
            b = query(rs, mid + 1, r, x);
        return cmp(a, b, x);
    }
} lct;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> y[i];
    lct.add(1, 0, 1e5, {-2 * x[1], x[1] * x[1] + y[1] * y[1]});
    for (int i = 1; i <= n; i++)
    {
        int ret = lct.query(1, 0, 1e5, a[i])(a[i]) + a[i] * a[i];
        lct.add(1, 0, 1e5, {-2 * x[i + 1], ret + x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1]});
        if (i == n)
            cout << ret;
    }
    return 0;
}
0