Submission #1191290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191290		MatteoArcari	Meetings (IOI18_meetings)	C++20	19 / 100	5589 ms	4932 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll Inf = 1e18;

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    int q = l.size();
    int n = h.size();
    vector<ll> ans(q, Inf);
    vector<ll> pre(n), suf(n);

    for (int i = 0; i < q; i++) {
        {
            ll sum = 0;
            deque<pair<ll, ll>> q;
            for (int j = l[i]; j <= r[i]; j++) {
                ll cnt = 1;
                while (!q.empty() && q.front().first <= h[j]) {
                    cnt += q.front().second;
                    sum -= q.front().first * q.front().second;
                    q.pop_front();
                }
                sum += cnt * h[j];
                q.push_front({h[j], cnt});
                pre[j] = sum;
            }
        }
        {
            ll sum = 0;
            deque<pair<ll, ll>> q;
            for (int j = r[i]; j >= l[i]; j--) {
                ll cnt = 1;
                while (!q.empty() && q.front().first <= h[j]) {
                    cnt += q.front().second;
                    sum -= q.front().first * q.front().second;
                    q.pop_front();
                }
                sum += cnt * h[j];
                q.push_front({h[j], cnt});
                suf[j] = sum;
            }
        }

        for (int j = l[i]; j <= r[i]; j++) {
            ans[i] = min(ans[i], pre[j] + suf[j] - h[j]);
        }
    }

    return ans;
}

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