Submission #167121

#	Time	Username	Problem	Language	Result	Execution time	Memory
167121		wleung_bvg	Meetings (IOI18_meetings)	C++14	100 / 100	3702 ms	381736 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);
}

using T = ll; const T NEG_INF = (numeric_limits<T>::lowest)() / 2;

T add(T a, T b) {
    if (a == NEG_INF || b == NEG_INF) return NEG_INF;
    return max(NEG_INF, a + b);
}

struct Line {
    T m, b;
    Line(T m = 0, T b = NEG_INF) : m(m), b(b) {}
    T eval(int x) const { return add(m * x, b); }
    void addConstant(T C) { b = add(b, C); }
    bool majorize(const Line &line, int l, int r) const { return eval(l) >= line.eval(l) && eval(r) >= line.eval(r); }
};

template <const int MAXN, const bool ONE_INDEXED, const bool maxHull> struct LiChaoTree {
    int N; Line TR[MAXN * 2]; T LZ[MAXN * 2];
    void init(int size) { N = size; fill(TR, TR + N * 2, Line()); fill(LZ, LZ + N * 2, 0); }
    void propagate(int cur, int tl, int tr) {
        if (LZ[cur] != 0) {
            int m = tl + (tr - tl) / 2, rc = cur + (m - tl + 1) * 2;
            TR[cur + 1].addConstant(LZ[cur]);
            LZ[cur + 1] = add(LZ[cur + 1], LZ[cur]);
            TR[rc].addConstant(LZ[cur]);
            LZ[rc] = add(LZ[rc], LZ[cur]);
            LZ[cur] = 0;
        }
    }
    void addConstant(int cur, int tl, int tr, int l, int r, T C) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) { TR[cur].addConstant(C); LZ[cur] = add(LZ[cur], C); return; }
        int m = tl + (tr - tl) / 2, rc = cur + (m - tl + 1) * 2; propagate(cur, tl, tr);
        addConstant(cur + 1, tl, m, l, r, C); addConstant(rc, m + 1, tr, l, r, C);
    }
    void addLine(int cur, int tl, int tr, Line line) {
        if (tl != tr) propagate(cur, tl, tr);
        if (line.majorize(TR[cur], tl, tr)) swap(line, TR[cur]);
        if (TR[cur].majorize(line, tl, tr)) return;
        if (TR[cur].eval(tl) < line.eval(tl)) swap(line, TR[cur]);
        int m = tl + (tr - tl) / 2, rc = cur + (m - tl + 1) * 2;
        if (line.eval(m) >= TR[cur].eval(m)) { swap(line, TR[cur]); addLine(cur + 1, tl, m, line); }
        else addLine(rc, m + 1, tr, line);
    }
    void addLineSegment(int cur, int tl, int tr, int l, int r, Line line) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) { addLine(cur, tl, tr, line); return; }
        int m = tl + (tr - tl) / 2, rc = cur + (m - tl + 1) * 2; propagate(cur, tl, tr);
        addLineSegment(cur + 1, tl, m, l, r, line); addLineSegment(rc, m + 1, tr, l, r, line);
    }
    T getMax(int cur, int tl, int tr, int x) {
        T ret = TR[cur].eval(x);
        if (tl == tr) return ret;
        int m = tl + (tr - tl) / 2, rc = cur + (m - tl + 1) * 2; propagate(cur, tl, tr);
        if (x <= m) return max(ret, getMax(cur + 1, tl, m, x));
        else return max(ret, getMax(rc, m + 1, tr, x));
    }
    void addConstant(int l, int r, T C) { addConstant(0, ONE_INDEXED, N - !ONE_INDEXED, l, r, maxHull ? C : -C); }
    void addLine(Line line) { addLine(0, ONE_INDEXED, N - !ONE_INDEXED, maxHull ? line : Line(-line.m, -line.b)); }
    void addLineSegment(Line line, int l, int r) {
        addLineSegment(0, ONE_INDEXED, N - !ONE_INDEXED, l, r, maxHull ? line : Line(-line.m, -line.b));
    }
    T getMax(int x) { T ret = getMax(0, ONE_INDEXED, N - !ONE_INDEXED, x); return maxHull ? ret : -ret; }
};

const int MAXN = 750005;

LiChaoTree<MAXN, 0, false> lLines, rLines;

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, LLONG_MAX);
    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);
    }
    lLines.init(N);
    rLines.init(N);
    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(lLines.getMax(L[i]) + (R[i] - m + 1) * hm, rLines.getMax(R[i]) + (m - L[i] + 1) * hm);
        if (l < m) lLines.addConstant(l, m - 1, (r - m + 1) * hm);
        if (m < r) rLines.addConstant(m + 1, r, (m - l + 1) * hm);
        lLines.addLineSegment(Line(-hm, (m < r ? lLines.getMax(m + 1) : 0) + (m + 1) * hm), l, m);
        rLines.addLineSegment(Line(hm, (l < m ? rLines.getMax(m - 1) : 0) - (m - 1) * hm), m, r);
    };
    solve(0, N - 1);
    return ans;
}

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