Submission #710628

#	Time	Username	Problem	Language	Result	Execution time	Memory
710628		Cyanmond	Meetings (IOI18_meetings)	C++17	41 / 100	2228 ms	11528 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using i64 = long long;
constexpr int inf = 1 << 30;

template <class M>
class LazySegmentTree {
    using T = typename M::T;
    using L = typename M::L;
    int n, logn, size;
    std::vector<T> data;
    std::vector<L> lazy;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }
    void all_apply(int i, const L &f) {
        data[i] = M::map(f, data[i]);
        if (i < size) lazy[i] = M::composite(f, lazy[i]);
    }
    void push(int i) {
        all_apply(2 * i, lazy[i]);
        all_apply(2 * i + 1, lazy[i]);
        lazy[i] = M::id();
    }

    public:
    LazySegmentTree(const std::vector<T> &vec) : n(vec.size()) {
        logn = 1;
        while ((1 << logn) < n) ++logn;
        size = 1 << logn;
        data.assign(2 * size, M::e());
        lazy.assign(size, M::id());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i > 0; --i) update(i);
    }

    void apply(int l, int r, const L &f) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2, r = r2;
        for (int d = 1; d <= logn; ++d) {
            if (((l >> d) << d) != l) update(l >> d);
            if (((r >> d) << d) != r) update((r - 1) >> d);
        }
    }

    T fold(int l, int r) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        T pl = M::e(), pr = M::e();
        while (l < r) {
            if (l & 1) pl = M::op(pl, data[l++]);
            if (r & 1) pr = M::op(data[--r], pr);
            l /= 2;
            r /= 2;
        }
        return M::op(pl, pr);
    }
};

struct Mon {
    using T = int;
    static T op(T a, T b) {
        return std::max(a, b);
    }
    static T e() {
        return -inf;
    }
    using L = int;
    static T map(L a, T b) {
        return a + b;
    }
    static L composite(L a, T b) {
        return a + b;
    }
    static L id() {
        return 0;
    }
};

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int N = (int)H.size(), Q = (int)L.size();
    const int maxH = *std::max_element(H.begin(), H.end());
    assert(maxH <= 20);
    for (auto &e : H) --e;
    std::vector<std::vector<std::pair<int, int>>> ranges(maxH);
    std::vector<int> initVec(N + 1);
    for (int x = 0; x < maxH; ++x) {
        int l = 0;
        for (int i = 0; i < N; ++i) {
            if (H[i] >= x) {
                if (l != i) {
                    ranges[x].push_back({l, i - 1});
                }
                l = i + 1;
            }
        }
        if (l != N) ranges[x].push_back({l, N - 1});
        for (const auto &[l, r] : ranges[x]) {
            initVec[l] += r - l + 1;
            initVec[r + 1] -= r - l + 1;
        }
    }
    for (int i = 0; i < N; ++i) initVec[i + 1] += initVec[i];
    initVec.pop_back();
    LazySegmentTree<Mon> seg(initVec);
    std::vector<i64> answer(Q);
    for (int i = 0; i < Q; ++i) {
        auto fixL = [&](int l, const std::pair<int, int> &range) {
            if (range.first >= l or range.second < l) return;
            seg.apply(l, range.second + 1, -(l - range.first));
        };
        auto fixR = [&](int r, const std::pair<int, int> &range) {
            if (range.first > r or range.second <= r) return;
            seg.apply(range.first, r + 1, -(range.second - r));
        };
        for (int x = 0; x < maxH; ++x) {
            auto itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(L[i], 0));
            if (itr != ranges[x].begin()) {
                --itr;
                fixL(L[i], *itr);
            }
            itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(R[i] + 1, 0));
            if (itr != ranges[x].begin()) {
                --itr;
                fixR(R[i], *itr);
            }
        }
        answer[i] = (R[i] - L[i] + 1) * maxH - seg.fold(L[i], R[i] + 1);

        auto revL = [&](int l, const std::pair<int, int> &range) {
            if (range.first >= l or range.second < l) return;
            seg.apply(l, range.second + 1, l - range.first);
        };
        auto revR = [&](int r, const std::pair<int, int> &range) {
            if (range.first > r or range.second <= r) return;
            seg.apply(range.first, r + 1, range.second - r);
        };
        for (int x = 0; x < maxH; ++x) {
            auto itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(L[i], 0));
            if (itr != ranges[x].begin()) {
                --itr;
                revL(L[i], *itr);
            }
            itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(R[i] + 1, 0));
            if (itr != ranges[x].begin()) {
                --itr;
                revR(R[i], *itr);
            }
        }
    }
    return answer;
}

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