제출 #755468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755468		boris_mihov	모임들 (IOI18_meetings)	C++17	19 / 100	5518 ms	1748 KiB

meetings

#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, q;
int a[MAXN];
llong prefix[MAXN];
llong suffix[MAXN];
std::stack <std::pair <int, llong>> st;
std::vector <llong> ans;

llong solveFor(int l, int r)
{
    if (l == r)
    {
        return a[l];
    }

    while (!st.empty()) st.pop();
    for (int i = l ; i <= r ; ++i)
    {
        while (!st.empty() && a[st.top().first] < a[i])
        {
            st.pop();
        }

        if (st.empty())
        {
            st.push({i, 1LL * (i - l + 1) * a[i]});
        } else
        {
            st.push({i, st.top().second + 1LL * (i - st.top().first) * a[i]});
        }

        prefix[i] = st.top().second;
    }

    while (!st.empty()) st.pop();
    for (int i = r ; i >= l ; --i)
    {
        while (!st.empty() && a[st.top().first] < a[i])
        {
            st.pop();
        }

        if (st.empty())
        {
            st.push({i, 1LL * (r - i + 1) * a[i]});
        } else
        {
            st.push({i, st.top().second + 1LL * (st.top().first - i) * a[i]});
        }

        suffix[i] = st.top().second;
    }

    llong ans = suffix[l];
    for (int i = l + 1 ; i <= r ; ++i)
    {
        ans = std::min(ans, prefix[i - 1] + suffix[i]);
    }

    return ans;
}

std::vector <llong> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
    n = H.size();
    for (int i = 0 ; i < n ; ++i)
    {
        a[i] = H[i];
    }

    q = L.size();
    ans.resize(q);
    for (int i = 0 ; i < q ; ++i)
    {
        ans[i] = solveFor(L[i], R[i]);
    }

    return ans;
}

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