Submission #167104

#	Time	Username	Problem	Language	Result	Execution time	Memory
167104		wleung_bvg	Meetings (IOI18_meetings)	C++14	19 / 100	5581 ms	30180 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

template <class T, class F> struct SparseTable {
    int N, lg; vector<vector<T>> ST; F op;
    void build() { for (int i = 0; i < lg - 1; i++) for (int j = 0; j < N; j++) ST[i + 1][j] = op(ST[i][j], ST[i][min(j + (1 << i), N - 1)]); }
    template <class It> SparseTable(It st, It en, F op) : N(en - st), lg(32 - __builtin_clz(N)), ST(lg, vector<T>(st, en)), op(op) { build(); }
    template <class It> SparseTable(It st, It en) : SparseTable(st, en, F()) {}
    // 0-indexed, inclusive
    T query(int l, int r) { int i = 31 - __builtin_clz(r - l + 1); return op(ST[i][l], ST[i][r - (1 << i) + 1]); }
};

template <class It, class F> auto makeSparseTable(It st, It en, F op) {
    return SparseTable<typename std::iterator_traits<It>::value_type, F>(st, en, op);
}

struct Line {
    ll m, b;
    int l, r;
    Line(ll m, ll b, int l, int r) : m(m), b(b), l(l), r(r) {}
};

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = sz(H),Q = sz(L);
    vector<int> P(N, 0);
    iota(P.begin(), P.end(), 0);
    auto ST = makeSparseTable(P.begin(), P.end(), [&] (const int &i, const int &j) { return H[i] > H[j] ? i : j; });
    vector<ll> ans(Q, INF);
    vector<vector<int>> queries(N);
    for (int i = 0; i < Q; i++) {
        if (L[i] == R[i]) ans[i] = H[L[i]];
        else queries[ST.query(L[i], R[i])].push_back(i);
    }
    vector<Line> lLines(N, Line(0, INF, N, -1)), rLines(N, Line(0, INF, N, -1));
    auto query = [&] (const vector<Line> &lines, ll x) {
        ll mn = INF;
        for (auto &&line : lines) if (line.l <= x && x <= line.r) mn = min(mn, line.m * x + line.b);
        return mn;
    };
    function<void(int, int)> solve = [&] (int l, int r) {
        if (l > r) return;
        int m = ST.query(l, r);
        ll hm = H[m];
        solve(l, m - 1);
        solve(m + 1, r);
        for (int i : queries[m]) ans[i] = min(query(lLines, L[i]) + (R[i] - m + 1) * hm, query(rLines, R[i]) + (m - L[i] + 1) * hm);
        ll lDelta = (r - m + 1) * hm, rDelta = (m - l + 1) * hm;
        for (int i = l; i <= m - 1; i++) lLines[i].b += lDelta;
        for (int i = m + 1; i <= r; i++) rLines[i].b += rDelta;
        lLines[m] = Line(-hm, (m < r ? query(lLines, m + 1) : 0) + (m + 1) * hm, l, m);
        rLines[m] = Line(hm, (l < m ? query(rLines, m - 1) : 0) - (m - 1) * hm, m, r);
    };
    solve(0, N - 1);
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40