Submission #292094

#	Time	Username	Problem	Language	Result	Execution time	Memory
292094		SamAnd	Meetings (IOI18_meetings)	C++17	19 / 100	5509 ms	7080 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, qq;

vector<ll> solv2(vector<int> H, vector<int> L, vector<int> R)
{
    vector<ll> v;
    for (int ii = 0; ii < qq; ++ii)
    {
        int l = L[ii];
        int r = R[ii];

        vector<ll> ans(n);
        for (int i = l; i <= r; ++i)
            ans[i] = 0;

        stack<pair<int, int> > s;
        ll yans = 0;
        for (int i = l; i <= r; ++i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans;
        }

        while (!s.empty())
            s.pop();
        yans = 0;
        for (int i = r; i >= l; --i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans - H[i];
        }

        yans = ans[l];
        for (int i = l; i <= r; ++i)
            yans = min(yans, ans[i]);
        v.push_back(yans);
    }
    return v;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R)
{
    n = sz(H);
    qq = sz(L);
    return solv2(H, L, R);
}

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