結果

問題 No.704 ゴミ拾い Medium
ユーザー vjudge1
提出日時 2025-03-21 20:09:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 1,500 ms
コード長 2,630 bytes
コンパイル時間 3,684 ms
コンパイル使用メモリ 276,332 KB
実行使用メモリ 29,440 KB
最終ジャッジ日時 2025-03-21 20:09:26
合計ジャッジ時間 10,371 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define F first
#define S second
#define Bout(x) (x ? "Yes" : "No")
#define DO(x) return x, void(0);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using mii = map<int, int>;
using ui = unsigned;
const int N = 3e5 + 5;
const int Md = 1e15 + 7;
int n, m;
int a[N], x[N], y[N];
struct LiChaoT {
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid ((tl + tr) >> 1)
    struct node {
        int k, b;
        node(int _k = 0, int _b = 1e15) : 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; }
    } seg[N << 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 tl, int tr, node val, int l, int r) {
        if (l <= tl && tr <= r) {
            if (seg[id] == val) return;
            if (cmp(seg[id], val, mid) == val) swap(seg[id], val);
            if (cmp(seg[id], val, tl) == val) add(ls, tl, mid, val, l, r);
            if (cmp(seg[id], val, tr) == val) add(rs, mid + 1, tr, val, l, r);
        }
        else {
            if (l <= mid) add(ls, tl, mid, val, l, r);
            if (mid < r) add(rs, mid + 1, tr, val, l, r);
        }
    }
    node qry(int id, int tl, int tr, int x) {
        if (tl == tr) return seg[id];
        node a = seg[id], b = (x <= mid ? qry(ls, tl, mid, x) : qry(rs, mid + 1, tr, x));
        return cmp(a, b, x);
    }
#undef mid
#undef ls
#undef rs
}T;
signed main() {
    FASTIO;
    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];
    T.add(1, 0, 2e5, { 1, y[0 + 1] - x[0 + 1] + 0 }, x[0 + 1], 2e5);
    T.add(1, 0, 2e5, { -1, y[0 + 1] + x[0 + 1] + 0 }, 0, x[0 + 1]);
    for (int i = 1; i <= n; i++) {
        int now = T.qry(1, 0, 2e5, a[i])(a[i]);
        T.add(1, 0, 2e5, { 1, y[i + 1] - x[i + 1] + now }, x[i + 1], 2e5);
        T.add(1, 0, 2e5, { -1, y[i + 1] + x[i + 1] + now }, 0, x[i + 1]);
        if (i == n) cout << now;
    }
    return 0;
}
/*
a[i] : ppl
x[i] : garbage X_i
y[i] : garbage Y_i

dp[i] = min(dp[j] + abs(x[j] - a[i]) + y[j])
x[i] < a[i] : min(dp[j] + a[i] - x[j] + y[j]) => min(a[i] + y[j] - x[j] + dp[j]) | x[i] -> N
x[i] > a[i] : min(dp[j] + x[j] - a[i] + y[i]) => min(-a[i] + y[j] + x[j] + dp[j]) | 0 -> x[i]


*/
0