Submission #765740

#	Time	Username	Problem	Language	Result	Execution time	Memory
765740		t6twotwo	Meetings (IOI18_meetings)	C++17	60 / 100	493 ms	233372 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = H.size(), Q = L.size();
    if (N <= 5000 && Q <= 5000) {
        vector<ll> ans(Q, inf);
        for (int i = 0; i < Q; i++) {
            vector<int> stk;
            vector<ll> A(N);
            for (int j = L[i]; j <= R[i]; j++) {
                while (!stk.empty() && H[stk.back()] <= H[j]) {
                    stk.pop_back();
                }
                if (stk.empty()) {
                    A[j] = 1LL * H[j] * (j - (L[i] - 1));
                } else {
                    A[j] = 1LL * H[j] * (j - stk.back()) + A[stk.back()];
                }
                stk.push_back(j);
            }
            stk.clear();
            vector<ll> B(N);
            for (int j = R[i]; j >= L[i]; j--) {
                while (!stk.empty() && H[stk.back()] <= H[j]) {
                    stk.pop_back();
                }
                if (stk.empty()) {
                    B[j] = 1LL * H[j] * ((R[i] + 1) - j);
                } else {
                    B[j] = 1LL * H[j] * (stk.back() - j) + B[stk.back()];
                }
                stk.push_back(j);
            }
            for (int j = L[i]; j <= R[i]; j++) {
                ans[i] = min(ans[i], A[j] + B[j] - H[j]);
            }
        }
        return ans;
    }
    vector LC(N, vector<int>(21, -1));
    for (int i = 0; i < N; i++) {
        if (i) {
            LC[i] = LC[i - 1];
        }
        LC[i][H[i]] = i;
    }
    vector RC(N, vector<int>(21, N));
    for (int i = N - 1; i >= 0; i--) {
        if (i < N - 1) {
            RC[i] = RC[i + 1];
        }
        RC[i][H[i]] = i;
    }
    vector<int> LS(N), LP(N), stk;
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && H[stk.back()] <= H[i]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            LP[i] = -1;
            LS[i] = H[i] * (i + 1);
        } else {
            LP[i] = stk.back();
            LS[i] = H[i] * (i - LP[i]) + LS[LP[i]];
        }
        stk.push_back(i);
    }
    vector<int> RS(N), RP(N); stk.clear();
    for (int i = N - 1; i >= 0; i--) {
        while (!stk.empty() && H[stk.back()] <= H[i]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            RP[i] = N;
            RS[i] = H[i] * (N - i);
        } else {
            RP[i] = stk.back();
            RS[i] = H[i] * (RP[i] - i) + RS[RP[i]];
        }
        stk.push_back(i);
    }
    vector<int> lg(N + 1);
    for (int i = 2; i <= N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    vector st(N, vector<int>(lg[N] + 1));
    for (int i = 0; i < N; i++) {
        st[i][0] = LS[i] + RS[i] - H[i];
    }
    for (int j = 0; j < lg[N]; j++) {
        for (int i = 0; i + (2 << j) <= N; i++) {
            st[i][j + 1] = min(st[i][j], st[i + (1 << j)][j]);
        }
    }
    auto query = [&](int l, int r) {
        int k = lg[r - l];
        return min(st[l][k], st[r - (1 << k)][k]);
    };
    vector<ll> ans(Q, 1e18);
    for (int q = 0; q < Q; q++) {
        for (int a = 1; a <= 20; a++) {
            for (int b = 1; b <= 20; b++) {
                int pa = RC[L[q]][a];
                int pb = LC[R[q]][b];
                if (pa > R[q] || pb < L[q] || LP[pa] >= L[q] || RP[pb] <= R[q]) {
                    continue;
                }
                int l = max(pa, LP[pb] + 1);
                int r = min(pb, RP[pa] - 1);
                if (l > r) {
                    continue;
                }
                int s = query(l, r + 1);
                if (LP[pa] == -1) {
                    s -= a * L[q];
                } else {
                    s -= a * (L[q] - 1 - LP[pa]);
                    s -= LS[LP[pa]];
                }
                if (RP[pb] == N) {
                    s -= b * (N - 1 - R[q]);
                } else {
                    s -= b * (RP[pb] - 1 - R[q]);
                    s -= RS[RP[pb]];
                }
                ans[q] = min(ans[q], 1ll * s);
            }
        }
    }
    return ans;
}

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