Submission #157074

#	Time	Username	Problem	Language	Result	Execution time	Memory
157074		rama_pang	모임들 (IOI18_meetings)	C++14	100 / 100	3618 ms	579384 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;

struct LiChaoSegmentTree {
    struct Line {
        lint m, c; //y = mx + c

        Line(): m(0), c(0) { }
        
        Line(lint M, lint C): m(M), c(C) { }
        
        inline lint get(lint x) {
            return (m * x) + c;
        }
    };

    lint n;
    vector<Line> tree;
    vector<lint> lazy;

    lint get_size(int n, int tl, int tr) {
        if (tl == tr) {
            return n;
        }

        int mid = (tl + tr) / 2;
        return max(get_size(n * 2, tl, mid), get_size(n * 2 + 1, mid + 1, tr));
    }

    void build(int n, int tl, int tr) {
        if (tl == tr) {
            tree[n] = Line();
            lazy[n] = 0;
            return;
        }
        
        int mid = (tl + tr) / 2;
        build(n * 2, tl, mid);
        build(n * 2 + 1, mid + 1, tr);
        
        tree[n] = Line(0, INF);
        lazy[n] = 0;
    }

    void build(int n) {
        this->n = n;
        
        lint sz = get_size(1, 1, n) + 1;
        tree.resize(sz);
        lazy.resize(sz);

        build(1, 1, n);
    }

    inline void push(int n) {
        if (lazy[n]) {
            tree[n * 2].c += lazy[n];
            tree[n * 2 + 1].c += lazy[n];
            lazy[n * 2] += lazy[n];
            lazy[n * 2 + 1] += lazy[n];
            lazy[n] = 0;
        }
    }

    void add(int n, int tl, int tr, int le, int ri, lint val) {
        if (tl > tr || tr < le || tl > ri) {
            return;
        } else if (le <= tl && tr <= ri) {
            tree[n].c += val;
            lazy[n] += val;
            return;
        }

        push(n);
        int mid = (tl + tr) / 2;
        add(n * 2, tl, mid, le, ri, val);
        add(n * 2 + 1, mid + 1, tr, le, ri, val);
    }

    inline void add(int le, int ri, lint val) {
        add(1, 1, n, le, ri, val);
    }

    void set_line(int n, int tl, int tr, int le, int ri, Line l) {
        if (tl > tr || tr < le || tl > ri) {
            return;
        } else if (le <= tl && tr <= ri) {
            lint A = l.get(tl), B = l.get(tr), C = tree[n].get(tl), D = tree[n].get(tr);
            if (A <= C && B <= D) {
                tree[n] = l;
                return;
            } else if (A >= C && B >= D) {
                return;
            } else {
                push(n);
                int mid = (tl + tr) / 2;

                if (A <= C) swap(l, tree[n]);
                
                if (l.get(mid) >= tree[n].get(mid)) {
                    set_line(n * 2 + 1, mid + 1, tr, le, ri, l);
                } else {
                    swap(l, tree[n]);
                    set_line(n * 2, tl, mid, le, ri, l);
                }

                return;
            }
        }

        push(n);
        int mid = (tl + tr) / 2;
        set_line(n * 2, tl, mid, le, ri, l);
        set_line(n * 2 + 1, mid + 1, tr, le, ri, l);
    }

    inline void set_line(int le, int ri, Line l) {
        set_line(1, 1, n, le, ri, l);
    }

    lint query(int n, int tl, int tr, int point) {
        lint ans = tree[n].get(point);
        
        if (tl == tr) {
            return ans;
        }

        push(n);
        int mid = (tl + tr) / 2;
        
        if (point <= mid) {
            return min(ans, query(n * 2, tl, mid, point));
        } else {
            return min(ans, query(n * 2 + 1, mid + 1, tr, point));
        }
    }

    inline lint query(int point) {
        if (point > n || point < 1) return INF;
        return query(1, 1, n, point);
    }

} LS, RS; //Left side (each point represents answer of L...MaxRange) and Right side (each point represents answers to MinRange...R)

/* Sparse Table for Range Maximum Query, stores Hi and i (height and index) */
struct SparseTable {

    vector<array<array<lint, 2>, 20>> sparse; 

    SparseTable() { }
    
    void build(vector<lint> &H) {
        lint N = H.size();
        sparse.resize(N);

        for (int i = 1; i < N; i++) {
            sparse[i][0] = {H[i], i};
        }
        
        for (int k = 1; k < 20; k++) {
            for (int i = 1; i < N; i++) {
                sparse[i][k] = max(sparse[i][k], sparse[i][k - 1]);
                if ((i + (1ll << (k - 1))) < N) sparse[i][k] = max(sparse[i][k], sparse[i + (1ll << (k - 1))][k - 1]);
            }
        }
    }

    inline lint query(int le, int ri) { //get index of highest mountain in range le...ri
        lint k = 31 - __builtin_clz(ri - le + 1);
        return (max(sparse[le][k], sparse[ri - (1 << k) + 1][k]))[1];
    }

} RMQ;


void solve(int le, int ri, vector<lint> &H, vector<lint> &L, vector<lint> &R, vector<lint> &ans, vector<vector<int>> &Qs) {
    if (le > ri) return;

    lint m = RMQ.query(le, ri);
    solve(le, m - 1, H, L, R, ans, Qs);
    solve(m + 1, ri, H, L, R, ans, Qs);

    for (auto i : Qs[m]) {
        lint opt1, opt2;
        opt1 = LS.query(L[i]) + ((R[i] - m + 1ll) * H[m]);
        opt2 = ((m - L[i] + 1ll) * H[m]) + RS.query(R[i]);

        ans[i] = min(opt1, opt2);
    }
    
    LS.add(le, m, (ri - m + 1ll) * H[m]);
    if (ri != m) LS.set_line(le, m, LiChaoSegmentTree::Line(-H[m], LS.query(m + 1) + H[m] * (m + 1ll)));

    RS.add(m, ri, (m - le + 1ll) * H[m]);
    if (le != m) RS.set_line(m, ri, LiChaoSegmentTree::Line(+H[m], RS.query(m - 1) - H[m] * (m - 1ll)));
    
    return;
}

vector<lint> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    vector<lint> H, L, R, ans;
    vector<vector<int>> Qs;
    lint N = h.size(), Q = l.size();
    Qs.resize(N + 1), ans.resize(Q);

    H.emplace_back(0);
    for (int i = 0; i < N; i++) {
        H.emplace_back(h[i]);
    }
    for (int i = 0; i < Q; i++) {
        L.emplace_back(l[i] + 1);
        R.emplace_back(r[i] + 1);
    }

    RMQ.build(H);
    for (int i = 0; i < Q; i++) {
        lint mx = RMQ.query(L[i], R[i] );
        Qs[mx].emplace_back(i);
    }
    
    LS.build(N);
    RS.build(N);
    solve(1, N, H, L, R, ans, Qs);
    
    return ans;
}

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