oj.uz

Submission #167121

# Submission time Handle Problem Language Result Execution time Memory
167121 2019-12-06T04:35:05 Z wleung_bvg Meetings (IOI18_meetings) C++14
100 / 100
 3702 ms 381736 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47224 KB Output is correct
2 Correct 119 ms 47608 KB Output is correct
3 Correct 47 ms 47608 KB Output is correct
4 Correct 46 ms 47608 KB Output is correct
5 Correct 46 ms 47648 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 47 ms 47736 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 45 ms 47864 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47224 KB Output is correct
2 Correct 119 ms 47608 KB Output is correct
3 Correct 47 ms 47608 KB Output is correct
4 Correct 46 ms 47608 KB Output is correct
5 Correct 46 ms 47648 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 47 ms 47736 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 45 ms 47864 KB Output is correct
10 Correct 52 ms 48228 KB Output is correct
11 Correct 52 ms 48248 KB Output is correct
12 Correct 52 ms 48152 KB Output is correct
13 Correct 52 ms 48240 KB Output is correct
14 Correct 52 ms 48768 KB Output is correct
15 Correct 51 ms 48240 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47224 KB Output is correct
2 Correct 95 ms 51548 KB Output is correct
3 Correct 328 ms 77044 KB Output is correct
4 Correct 291 ms 65904 KB Output is correct
5 Correct 231 ms 76912 KB Output is correct
6 Correct 319 ms 80880 KB Output is correct
7 Correct 342 ms 84208 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47224 KB Output is correct
2 Correct 95 ms 51548 KB Output is correct
3 Correct 328 ms 77044 KB Output is correct
4 Correct 291 ms 65904 KB Output is correct
5 Correct 231 ms 76912 KB Output is correct
6 Correct 319 ms 80880 KB Output is correct
7 Correct 342 ms 84208 KB Output is correct
8 Correct 309 ms 66972 KB Output is correct
9 Correct 244 ms 66800 KB Output is correct
10 Correct 277 ms 66928 KB Output is correct
11 Correct 290 ms 65776 KB Output is correct
12 Correct 233 ms 65776 KB Output is correct
13 Correct 294 ms 65904 KB Output is correct
14 Correct 319 ms 78192 KB Output is correct
15 Correct 277 ms 65792 KB Output is correct
16 Correct 355 ms 78576 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47224 KB Output is correct
2 Correct 119 ms 47608 KB Output is correct
3 Correct 47 ms 47608 KB Output is correct
4 Correct 46 ms 47608 KB Output is correct
5 Correct 46 ms 47648 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 47 ms 47736 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 45 ms 47864 KB Output is correct
10 Correct 52 ms 48228 KB Output is correct
11 Correct 52 ms 48248 KB Output is correct
12 Correct 52 ms 48152 KB Output is correct
13 Correct 52 ms 48240 KB Output is correct
14 Correct 52 ms 48768 KB Output is correct
15 Correct 51 ms 48240 KB Output is correct
16 Correct 41 ms 47224 KB Output is correct
17 Correct 95 ms 51548 KB Output is correct
18 Correct 328 ms 77044 KB Output is correct
19 Correct 291 ms 65904 KB Output is correct
20 Correct 231 ms 76912 KB Output is correct
21 Correct 319 ms 80880 KB Output is correct
22 Correct 342 ms 84208 KB Output is correct
23 Correct 309 ms 66972 KB Output is correct
24 Correct 244 ms 66800 KB Output is correct
25 Correct 277 ms 66928 KB Output is correct
26 Correct 290 ms 65776 KB Output is correct
27 Correct 233 ms 65776 KB Output is correct
28 Correct 294 ms 65904 KB Output is correct
29 Correct 319 ms 78192 KB Output is correct
30 Correct 277 ms 65792 KB Output is correct
31 Correct 355 ms 78576 KB Output is correct
32 Correct 2340 ms 196528 KB Output is correct
33 Correct 1685 ms 199440 KB Output is correct
34 Correct 2120 ms 197632 KB Output is correct
35 Correct 2558 ms 197100 KB Output is correct
36 Correct 1694 ms 197836 KB Output is correct
37 Correct 2120 ms 197932 KB Output is correct
38 Correct 2925 ms 290024 KB Output is correct
39 Correct 2918 ms 290168 KB Output is correct
40 Correct 2769 ms 206900 KB Output is correct
41 Correct 3702 ms 380140 KB Output is correct
42 Correct 3591 ms 381736 KB Output is correct
43 Correct 3653 ms 381716 KB Output is correct
44 Correct 3410 ms 289884 KB Output is correct