結果

問題 No.705 ゴミ拾い Hard
ユーザー vjudge1
提出日時 2025-03-24 16:25:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 507 ms / 1,500 ms
コード長 3,590 bytes
コンパイル時間 2,300 ms
コンパイル使用メモリ 201,072 KB
実行使用メモリ 34,988 KB
最終ジャッジ日時 2025-03-24 16:25:40
合計ジャッジ時間 12,619 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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 2e18;
        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};
            }
        }
    }
};
struct T {
	node tree[N << 2];
	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 (cur.typ == 0 || cur.typ == 3 || (cur.typ == 1 && (cur.x1 < tl || cur.x1 > tr)) || (cur.typ == 2 && (cur.x1 < tl || cur.x1 > tr) && (cur.x2 < tl || cur.x2 > 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;
	            update(ls(i), tl, tm, l, r, p);
	            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));
	}	
} t1, t2;
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];
    t2.update(1, 0, N - 5, x[1], N - 5, {-3 * x[1], 3 * x[1] * x[1], -x[1] * x[1] * x[1] + y[1] * y[1] * y[1] + dp[0], 1});
    t1.update(1, 0, N - 5, 0, x[1], {3 * x[1], -3 * x[1] * x[1], x[1] * x[1] * x[1] + y[1] * y[1] * y[1] + dp[0], 1});
    for (int i = 1; i <= n; i++) {
    	dp[i] = min(t2.query(1, 0, N - 5, a[i]) + a[i] * a[i] * a[i], t1.query(1, 0, N - 5, a[i]) - a[i] * a[i] * a[i]);
    	t2.update(1, 0, N - 5, x[i + 1], N - 5, {-3 * x[i + 1], 3 * x[i + 1] * x[i + 1], -x[i + 1] * x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] * y[i + 1] + dp[i], 1});
   		t1.update(1, 0, N - 5, 0, x[i + 1], {3 * x[i + 1], -3 * x[i + 1] * x[i + 1], x[i + 1] * x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] * y[i + 1] + dp[i], 1});
	}
	cout << dp[n];
    return 0;
}
0