Submission #1011754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011754		boris_mihov	Meetings (IOI18_meetings)	C++17	19 / 100	5525 ms	19944 KiB

meetings

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

typedef long long llong;
const int MAXN = 750000 + 10;
const llong INF = 4e18;
const int INTINF = 2e9;

int n, q;
int a[MAXN];
struct Query
{
    int l, r;
    int idx;
};

Query query[MAXN];
llong answer[MAXN];
llong prefMAX[MAXN];
llong suffMAX[MAXN];

void solve()
{
    for (int idx = 1 ; idx <= q ; ++idx)
    {
        int l = query[idx].l;
        int r = query[idx].r;
        std::stack <std::array <int, 3>> st;
        prefMAX[l - 1] = suffMAX[r + 1] = 0;
        st.push({l - 1, 0, INTINF});

        for (int i = l ; i <= r ; ++i)
        {
            prefMAX[i] = prefMAX[i - 1];
            while (st.size() && st.top()[2] < a[i])
            {
                prefMAX[i] -= 1LL * st.top()[1] * st.top()[2];
                st.pop();
            }

            prefMAX[i] += 1LL * (i - st.top()[0]) * a[i];
            st.push({i, (i - st.top()[0]), a[i]});
        }

        while (st.size()) st.pop();
        st.push({r + 1, 0, INTINF});

        for (int i = r ; i >= l ; --i)
        {
            suffMAX[i] = suffMAX[i + 1];
            while (st.size() && st.top()[2] < a[i])
            {
                suffMAX[i] -= 1LL * st.top()[1] * st.top()[2];
                st.pop();
            }

            suffMAX[i] += 1LL * (st.top()[0] - i) * a[i];
            st.push({i, (st.top()[0] - i), a[i]});
        }

        answer[idx] = INF;
        for (int i = l ; i <= r ; ++i)
        {
            answer[idx] = std::min(answer[idx], prefMAX[i] + suffMAX[i] - a[i]);
        }
    }
}

std::vector <llong> minimum_costs(std::vector <int> H, std::vector <int> L, std::vector <int> R)
{
    n = H.size();
    q = L.size();

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = H[i - 1];
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        query[i].l = L[i - 1] + 1;
        query[i].r = R[i - 1] + 1;
    }

    solve();
    std::vector <llong> sol;
    for (int i = 1 ; i <= q ; ++i)
    {
        sol.push_back(answer[i]);
    }

    return sol;
}

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