Submission #763995

#	Time	Username	Problem	Language	Result	Execution time	Memory
763995		t6twotwo	Meetings (IOI18_meetings)	C++17	36 / 100	509 ms	11692 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<int> two;
    for (int i = 0; i < N; i++) {
        if (H[i] == 2) {
            two.push_back(i);
        }
    }
    int M = two.size();
    int lg = __lg(M);
    vector st(M, vector<int>(lg + 1));
    for (int i = 1; i < M; i++) {
        st[i][0] = two[i] - two[i - 1] - 1;
    }
    for (int j = 0; j < lg; j++) {
        for (int i = 0; i + (2 << j) <= M; i++) {
            st[i][j + 1] = max(st[i][j], st[i + (1 << j)][j]);
        }
    }
    auto query = [&](int l, int r) {
        if (l == r) {
            return 0;
        }
        int k = __lg(r - l);
        return max(st[l][k], st[r - (1 << k)][k]);
    };
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int l = lower_bound(two.begin(), two.end(), L[i]) - two.begin();
        int r = upper_bound(two.begin(), two.end(), R[i]) - two.begin() - 1;
        if (l == M || two[l] > R[i]) {
            ans[i] = R[i] - L[i] + 1;
            continue;
        }
        ans[i] = max(ans[i], two[l] - L[i]);
        ans[i] = max(ans[i], R[i] - two[r]);
        ans[i] = max(ans[i], query(l + 1, r + 1));
        ans[i] = 2 * (R[i] - L[i] + 1) - ans[i];
    }
    vector<ll> lans(Q);
    for (int i = 0; i < Q; i++) {
        lans[i] = ans[i];
    }
    return lans;
}

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