Submission #426437

#	Time	Username	Problem	Language	Result	Execution time	Memory
426437		KoD	Meetings (IOI18_meetings)	C++17	0 / 100	4226 ms	786436 KiB

meetings

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

using ll = long long;
template <class T> using Vec = std::vector<T>;

constexpr ll INF = std::numeric_limits<ll>::max();

template <class T> void setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
    }
}

template <class T> void setmax(T& x, const T& y) {
    if (x < y) {
        x = y;
    }
}

struct RMQ {
    Vec<Vec<int>> table;
    RMQ(const Vec<int>& vec) {
        const int n = (int) vec.size();
        int k = 0;
        while ((1 << k) <= n) {
            k += 1;
        }
        table.resize(k);
        table[0] = vec;
        for (int h = 0; h < k - 1; ++h) {
            const int len = n - (1 << (h + 1)) + 1;
            table[h + 1].resize(len);
            for (int i = 0; i < len; ++i) {
                table[h + 1][i] = std::max(table[h][i], table[h][i + (1 << h)]);
            }
        }
    }
    int fold(const int l, const int r) {
        if (l >= r) {
            return std::numeric_limits<int>::min();
        }
        const int h = 31 - __builtin_clz(r - l);
        return std::max(table[h][l], table[h][r - (1 << h)]);
    }
};

Vec<ll> minimum_costs(Vec<int> H, Vec<int> L, Vec<int> R) {
    const int N = (int) H.size();
    const int Q = (int) L.size();
    if (N >= 5000) {
        Vec<Vec<int>> cost(N, Vec<int>(N));
        for (int i = 0; i < N; ++i) {
            int max = H[i];
            cost[i][i] = max;
            for (int j = i - 1; j >= 0; --j) {
                setmax(max, H[j]);
                cost[i][j] = max;
            }
            max = H[i];
            for (int j = i + 1; j < N; ++j) {
                setmax(max, H[j]);
                cost[i][j] = max;
            }
        }
        Vec<Vec<ll>> sum(N, Vec<ll>(N + 1));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                sum[i][j + 1] = sum[i][j] + cost[i][j];
            }
        }
        Vec<ll> ret(Q, INF);
        for (int i = 0; i < Q; ++i) {
            const int l = L[i];
            const int r = R[i] + 1;
            for (int j = l; j < r; ++j) {
                setmin(ret[i], sum[j][r] - sum[j][l]);
            }
        }
        return ret;
    } else {
        Vec<std::pair<int, int>> one;
        {
            int l = 0;
            while (l < N) {
                if (H[l] == 2) {
                    l += 1;
                    continue;
                }
                int r = l;
                while (r < N and H[r] == 1) {
                    r += 1;
                }
                one.emplace_back(l, r);
                l = r;
            }
        }
        const int M = (int) one.size();
        Vec<int> len(M + 1);
        for (int i = 0; i < M; ++i) {
            len[i] = one[i].second - one[i].first;
        }
        RMQ rmq(len);
        Vec<ll> ret(Q);
        for (int i = 0; i < Q; ++i) {
            R[i] += 1;
            const auto lb = std::lower_bound(one.begin(), one.end(), std::pair<int, int>(L[i], 0)) - one.begin();
            const auto ub = std::lower_bound(one.begin(), one.end(), std::pair<int, int>(R[i], 0)) - one.begin();
            int max = 0;
            if (lb > 0) {
                setmax(max, std::clamp(one[lb - 1].second, L[i], R[i]) - L[i]);
            }
            if (lb < ub) {
                setmax(max, std::min(one[ub - 1].second, R[i]) - one[ub - 1].first);
                setmax(max, rmq.fold(lb, ub - 1));
            }
            ret[i] = (R[i] - L[i]) * 2 - max;
        }
        return ret;
    }
}

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