結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-25 17:54:52
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,486 bytes
コンパイル時間 5,324 ms
コンパイル使用メモリ 212,684 KB
実行使用メモリ 21,796 KB
最終ジャッジ日時 2025-03-25 17:55:06
合計ジャッジ時間 13,639 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
using ll = long long;
const double eps = 1e-7;
/*
typ:
    0: no cross point
    1: only one
    2: two points
    3: same function
*/
struct point {
    double x1, x2;
    int typ;
};
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
struct node {
    ll a, b, c;
    bool flag;
    ll operator () (int x) {
        if (!flag) return LLONG_MAX;
        return a * x * x + b * x + c;
    }
    friend point cross(node x, node y) {
        ll a = x.a - y.a, b = x.b - y.b, c = x.c - y.c;
        if (a == 0) {
            if (b == 0) {
                if (c == 0) {
                    return {0, 0, 3};
                }
                else {
                    return {0, 0, 0};
                }
            }
            else {
                return {-1.0 * c / b, 0, 1};
            }
        }
        else {
            ll delta = b * b - 4 * a * c;
            if (delta < 0) return {0, 0, 0};
            else if (delta == 0) return {-1.0 * b / (2 * a), 0, 1};
            else {
                double x1 = 1.0 * (-1.0 * b + sqrtl(delta)) / (2 * a);
                double x2 = 1.0 * (-1.0 * b - sqrtl(delta)) / (2 * a);
                if (x1 > x2) swap(x1, x2);
                return {x1, x2, 2};
            }
        }
    }
} tree[N << 2];
bool in(point cur, int l, int r) {
	return (cur.typ == 1 && (l <= cur.x1 && cur.x1 <= r) || cur.typ == 2 && (l <= cur.x1 && cur.x1 <= r) && (l <= cur.x2 && cur.x2 <= r));
} 
bool in2(point cur, int l, int r) {
	return (cur.typ == 1 && (l <= cur.x1 && cur.x1 <= r) || cur.typ == 2 && ((l <= cur.x1 && cur.x1 <= r) || (l <= cur.x2 && cur.x2 <= r)));
}
void update(int i, int tl, int tr, int l, int r, node p) {
    if (l <= tl && tr <= r) {
        if (!tree[i].flag) {
            tree[i].a = p.a;
            tree[i].b = p.b;
            tree[i].c = p.c;
            tree[i].flag = 1;
            return;
        }
        auto cur = cross(p, tree[i]);
        if (!in(cur, tl, tr)) {
            if (p(tl) - tree[i](tl) < 0 && p(tr) - tree[i](tr) < 0)
                tree[i].a = p.a, tree[i].b = p.b, tree[i].c = p.c;
        }
        else {
            int tm = tl + tr >> 1;
            if (p(tm) - tree[i](tm) < 0)
            	swap(p.a, tree[i].a), swap(p.b, tree[i].b), swap(p.c, tree[i].c);
            if (in2(cur, tl, tm))
            	update(ls(i), tl, tm, l, r, p);
            if (in2(cur, tm + 1, tr))
            	update(rs(i), tm + 1, tr, l, r, p);
        }
    }
    else {
        int tm = tl + tr >> 1;
        if (l <= tm)
            update(ls(i), tl, tm, l, r, p);
        if (r > tm)
            update(rs(i), tm + 1, tr, l, r, p);
    }
}
ll query(int i, int tl, int tr, int pos) {
    if (tl == tr) return tree[i](pos);
    int tm = tl + tr >> 1;
    ll ans = tree[i](pos);
    if (pos <= tm)
        return min(ans, query(ls(i), tl, tm, pos));
    else
        return min(ans, query(rs(i), tm + 1, tr, pos));
}
ll a[N * 3], x[N * 3], y[N * 3], dp[N * 3];
int main() {
    int n;
	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];
    update(1, 0, N - 5, 0, N - 5, {1, -2 * x[1], x[1] * x[1] + y[1] * y[1], 1});
    for (int i = 1; i <= n; i++) {
        dp[i] = query(1, 0, N - 5, a[i]);
        update(1, 0, N - 5, 0, N - 5, {1, -2 * x[i + 1], x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] + dp[i], 1});
    }
    cout << dp[n];
    return 0;
}
0