Submission #755473

#	Time	Username	Problem	Language	Result	Execution time	Memory
755473		boris_mihov	Meetings (IOI18_meetings)	C++17	0 / 100	15 ms	3040 KiB

meetings

#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#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;
    }

    prefix[l - 1] = 0;
    suffix[r + 1] = 0;

    int opt = l;
    llong ans = suffix[l];
    for (int i = l + 1 ; i <= r ; ++i)
    {
        if (ans > prefix[i - 1] + suffix[i])
        {
            ans = prefix[i - 1] + suffix[i];
            opt = i;
        }
    }

    for (int i = l ; i < opt ; ++i)
    {
        assert(prefix[i - 1] + suffix[i] >= prefix[i] + suffix[i + 1]);
    }

    for (int i = opt ; i <= r ; ++i)
    {
        assert(prefix[i - 1] + suffix[i] <= prefix[i] + suffix[i + 1]);
    }

    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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40