Submission #740414

#	Time	Username	Problem	Language	Result	Execution time	Memory
740414		danikoynov	Meetings (IOI18_meetings)	C++14	19 / 100	5538 ms	8188 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 7.5e5 + 10;
int n, q;
ll h[maxn];

ll calc(int pivot, int left, int right)
{
    ll mx = 0, ans = 0;
    for (int i = pivot; i >= left; i --)
    {
        mx = max(mx, h[i]);
        ans += mx;
    }

    mx = h[pivot];
    for (int i = pivot + 1; i <= right; i ++)
    {
        mx = max(mx, h[i]);
        ans += mx;
    }

    return ans;
}


ll pref[maxn], suff[maxn];
ll query(int left, int right)
{
    ll ans = 1e18;

    /**for (int pivot = left; pivot <= right; pivot ++)
    {
        ll cur = calc(pivot, left, right);
        cout << cur << " ";
        ans = min(ans, calc(pivot, left, right));
    }
    cout << endl;*/

    stack < int > st;
    ll sum = 0;
    for (int i = left; i <= right; i ++)
    {
        while(!st.empty() && h[st.top()] < h[i])
        {
            int val = st.top();
            st.pop();
            int bef = left - 1;
            if (!st.empty())
                bef = st.top();
            sum = sum - (ll)(val - bef) * h[val];
        }

        int bef = left - 1;
        if (!st.empty())
        {
            bef = st.top();
        }
            sum = sum + (ll)(i - bef) * h[i];

        st.push(i);

        pref[i] = sum;
        ///cout << pref[i] << " ";
    }
    ///cout << endl;

    while(!st.empty())
        st.pop();
    sum = 0;
    for (int i = right; i >= left; i --)
    {
        while(!st.empty() && h[st.top()] < h[i])
        {
            int val = st.top();
            st.pop();
            int aft = right + 1;
            if (!st.empty())
                aft = st.top();
            sum = sum - (ll)(aft - val) * h[val];
        }

        int aft = right + 1;
        if (!st.empty())
        {
            aft = st.top();
        }
            sum = sum + (ll)(aft - i) * h[i];

        st.push(i);
        suff[i] = sum;
    }

    for (int i = left; i <= right; i ++)
    {
        ans = min(ans, pref[i] + suff[i] - h[i]);
    }

    return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                vector<int> R)
{
    n = H.size();
    q = L.size();
    for (int i = 0; i < n; i ++)
    {
        h[i] = H[i];
    }

    vector < ll > res(q);
    for (int i = 0; i < q; i ++)
    {
        res[i] = query(L[i], R[i]);
    }
    return res;
}

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