Submission #996806

#	Time	Username	Problem	Language	Result	Execution time	Memory
996806		violet_valley	Building Bridges (CEOI17_building)	C++17	30 / 100	3014 ms	6152 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1 << (i))
#define FULL(i) (MASK(i) - 1)
#define __builtin_popcount __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T, class T2>
ostream &operator<<(ostream &o, pair<T, T2> p)
{
    o << "(" << p.first << ", " << p.second << ")";
    return o;
}
const int M = 1e5 + 5;
ll f[M], h[M], w[M], pre[M];
template<
  typename T,  // for segment & coordinates data types, e.g. long long
  typename TM  // for intermediate computations, e.g. __int128_t
> struct LiChao {
    LiChao(const vector<T>& _xs) : xs(_xs) {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        n = xs.size();
        head = 1;
        while (head < n) head <<= 1;

        lines.assign(head * 2, {0, 0, -1, false});
        xyz.resize(head * 2);
        for (int i = 0; i < n; i++) {
            xyz[head + i] = {xs[i], xs[i], xs[i]};
        }
        for (int i = head - 1; i; i--) {
            int l = i*2, r = i*2 + 1;
            xyz[i] = {
                std::get<0>(xyz[l]),
                std::get<0>(xyz[r]),
                std::get<2>(xyz[r]),
            };
        }
    }

    void add_line(T a, T b, int idx = -1) {
        ql = 0, qr = n;
        if (ql >= qr) return;
        rec(1, 0, head, Line{a, b, idx, true});
    }

    void add_segment(T left, T right, T a, T b, int idx = -1) {
        ql = std::lower_bound(xs.begin(), xs.end(), left) - xs.begin();
        qr = std::lower_bound(xs.begin(), xs.end(), right) - xs.begin();
        if (ql >= qr) return;
        rec(1, 0, head, Line{a, b, idx, true});
    }

    struct Result {
        T line_a, line_b;
        int line_id;
        bool is_valid;  // if false -> result is INFINITY
        TM minval;
    };

    Result get(T x) {
        int i = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        assert(i < n && xs[i] == x);
        return get(i, x);
    }

// private:
    int n, head;
    vector<T> xs;  // coordinates of all get queries

    struct Line {
        T a, b;  // a*x + b
        int id;
        bool is_valid;
        TM f(T x) const { return TM(a) * x + b; }
    };
    vector<Line> lines;

    vector<tuple<T, T, T>> xyz;  // <left, mid, right>

    int ql, qr;
    void rec(int i, int l, int r, Line new_line) {
        const int mid = (l + r) / 2;

        if (l >= qr || r <= ql) {
            return;
        } else if (ql <= l && r <= qr) {
            if (!lines[i].is_valid) {
                lines[i] = new_line;
                return;
            }

            auto [x, y, z] = xyz[i];
            bool upd_x = lines[i].f(x) > new_line.f(x);
            bool upd_y = lines[i].f(y) > new_line.f(y);
            bool upd_z = lines[i].f(z) > new_line.f(z);

            if (upd_x && upd_y && upd_z) {
                lines[i] = new_line;
                return;
            }
            if (upd_y && upd_z) {
                std::swap(lines[i], new_line);
                rec(i*2, l, mid, new_line);
            } else if (upd_x && upd_y) {
                std::swap(lines[i], new_line);
                rec(i*2 + 1, mid, r, new_line);
            } else if (upd_x) {
                rec(i*2, l, mid, new_line);
            } else if (upd_z) {
                rec(i*2+1, mid, r, new_line);
            } else {
                return;
            }
        } else {
            if (ql < mid) rec(i*2, l, mid, new_line);
            if (qr > mid) rec(i*2+1, mid, r, new_line);
        }
    }

    Result get(int i, T x) {
        i += head;
        Line res = lines[i];
        TM val = res.is_valid ? res.f(x) : 0;
        for (i /= 2; i; i /= 2) {
            if (!lines[i].is_valid) continue;
            TM tmp = lines[i].f(x);
            if (!res.is_valid || tmp < val) res = lines[i], val = tmp;
        }
        return {res.a, res.b, res.id, res.is_valid, val};
    }
};
ll sqr(ll x)
{
    return x * x;
}
signed main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
        cin >> w[i];
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + w[i];
    vector <ll> xCods;
    for (int i = 1; i <= n; ++i)
        xCods.push_back(h[i]);
    LiChao<ll, ll> st(xCods);
    for (int i = 2; i <= n; ++i)
    {
        int p = i - 1;
        st.add_line(-2 * h[p], sqr(h[p]) + f[p] - pre[p]);
        for (int j = 1; j < i; ++j)
            f[i] = sqr(h[i]) + pre[i - 1] + st.get(h[i]).minval;
    }
    cout << f[n];
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40