Submission #705406

#	Time	Username	Problem	Language	Result	Execution time	Memory
705406		piOOE	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	340 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Line {
    mutable double k, b, p;
    Line(double k, double m, double p = 0) : k(k), b(m), p(p) {}
    Line() = default;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(double x) const { return p < x; }
};

// (for doubles, use inf = nl<db>::max(), div(a,b) = a/b)
// query(x)->max, so if you want min => add -k and -b
// source: codeforces.com/blog/entry/11155?#comment-688428
class LineContainer : multiset<Line, less<>> {
    static constexpr double INF_cht = numeric_limits<double>::max();

    double div(double a, double b) { // floored division
        return a / b;
    }

    bool intersect(iterator x, iterator y) {
        if (y == end()) {
            return x->p = INF_cht, 0;
        }
        if (x->k == y->k) {
            x->p = x->b > y->b ? INF_cht : -INF_cht;
        } else {
            x->p = div(y->b - x->b, x->k - y->k);
        }
        return x->p >= y->p;
    }

public:
    void add(double k, double m) {
        k = -k, m = -m;
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (intersect(y, z)) {
            z = erase(z);
        }
        if (x != begin() && intersect(--x, y)) {
            intersect(x, y = erase(y));
        }
        while ((y = x) != begin() && (--x)->p >= y->p) {
            intersect(x, erase(y));
        }
    }

    int siz() {
        return size();
    }

    double query(double x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return -(l.k * x + l.b);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    auto solve = [&](vector<pair<int, int>> row, vector<pair<int, int>> column) -> ll {
        sort(row.rbegin(), row.rend());
        sort(column.rbegin(), column.rend());

        int n = row.size();
        int m = column.size();

        vector<int> x(n), y(m);
        vector<ll> a(n), b(m);

        for (int i = 0; i < n; ++i) {
            tie(a[i], x[i]) = row[i];
        }

        for (int j = 0; j < m; ++j) {
            tie(b[j], y[j]) = column[j];
        }

        if (x.front() > x.back()) {
            for (int &c: x) {
                c *= -1;
            }
        }

        if (y.front() >= y.back()) {
            for (int &c: y) {
                c *= -1;
            }
        }

        assert(is_sorted(x.begin(), x.end()));
        assert(is_sorted(y.begin(), y.end()));
        assert(is_sorted(a.rbegin(), a.rend()));
        assert(is_sorted(b.rbegin(), b.rend()));

        ll ans = (x.back() - x.front()) * b[m - 1] + (y.back() - y.front()) * a[0];

        LineContainer cht;

        for (int i = 0; i < n; ++i) {
            cht.add(x[i] - x[0], a[i] - a[0]);
        }

        for (int j = m - 2; j >= 0; --j) {
            ans += cht.query(double(b[j] - b[j + 1]) / (y[j + 1] - y[j])) * (y[j + 1] - y[j]);
        }

        return ans;
    };

    int h, w;
    cin >> h >> w;

    vector<int> a(h), b(w);

    for (int i = 0; i < h; ++i) {
        cin >> a[i];
    }

    for (int j = 0; j < w; ++j) {
        cin >> b[j];
    }

    constexpr int inf = 1e9 + 7;

    vector<int> pref(h + 1, inf), suf(h + 1, inf);

    vector<int> rows, columns;

    for (int i = 0; i < h; ++i) {
        pref[i + 1] = min(pref[i], a[i]);
    }

    for (int i = h - 1; i >= 0; --i) {
        suf[i] = min(a[i], suf[i + 1]);
    }

    for (int i = 0; i < h; ++i) {
        if (pref[i] > a[i] || suf[i + 1] > a[i]) {
            rows.push_back(i);
        }
    }

    pref.assign(w + 1, inf), suf.assign(w + 1, inf);

    for (int i = 0; i < w; ++i) {
        pref[i + 1] = min(pref[i], b[i]);
    }

    for (int i = w - 1; i >= 0; --i) {
        suf[i] = min(b[i], suf[i + 1]);
    }

    for (int i = 0; i < w; ++i) {
        if (pref[i] > b[i] || suf[i + 1] > b[i]) {
            columns.push_back(i);
        }
    }

    int n = rows.size(), m = columns.size();

    int lx = 0, rx = n - 1;
    int ly = 0, ry = m - 1;

    while (lx < n - 1 && a[rows[lx + 1]] < a[rows[lx]]) {
        lx += 1;
    }

    while (rx > 0 && a[rows[rx - 1]] < a[rows[rx]]) {
        rx -= 1;
    }

    assert(lx <= rx);
    assert(abs(rx - lx) <= 1);

    while (ly < m - 1 && b[columns[ly + 1]] < b[columns[ly]]) {
        ly += 1;
    }

    while (ry > 0 && b[columns[ry - 1]] < b[columns[ry]]) {
        ry -= 1;
    }

    assert(ly <= ry);
    assert(abs(ry - ly) <= 1);

    vector<pair<int, int>> row, column;

    for (int i = 0; i <= lx; ++i) {
        row.emplace_back(a[rows[i]], rows[i]);
    }

    for (int i = 0; i <= ly; ++i) {
        column.emplace_back(b[columns[i]], columns[i]);
    }

    ll ans = solve(row, column);

    row.clear(), column.clear();

    for (int i = rx; i < n; ++i) {
        row.emplace_back(a[rows[i]], rows[i]);
    }

    for (int i = ry; i < m; ++i) {
        column.emplace_back(b[columns[i]], columns[i]);
    }

    ans += solve(row, column);

    ans += 1LL * (rows[rx] - rows[lx]) * b[columns[lx]];

    ans += 1LL * (columns[ry] - columns[ly]) * a[rows[lx]];

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60