Submission #421995

#	Time	Username	Problem	Language	Result	Execution time	Memory
421995		timmyfeng	Meetings (IOI18_meetings)	C++17	0 / 100	21 ms	2208 KiB

meetings

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

#include "meetings.h"

const int N = 750000, L = __lg(N) + 1;

struct range {
    long long mini, sum;
    int size, par;
} nxt_l[N], nxt_r[N];

vector<int> h;

range combine(range l, range r) {
    if (r.par == -1) {
        return {0, 0, 0, -1};
    } else {
        return {
            min(l.mini + r.sum, (long long) h[l.par] * l.size + r.mini),
            l.sum + r.sum,
            l.size + r.size,
            r.par
        };
    }
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    int n = h.size(), q = l.size();
    ::h = h;

    for (int i = 0; i < n; ++i) {
        nxt_l[i].par = nxt_r[i].par = -1;
    }

    vector<int> less, greater;
    for (int i = 0; i < n; ++i) {
        while (!less.empty() && h[less.back()] < h[i]) {
            int j = less.back();
            less.pop_back();

            range mini = {0, 0, 0, i - 1};
            while (true) {
                range temp = combine(mini, nxt_l[mini.par]);
                if (temp.par < j) {
                    break;
                }
                mini = temp;
            }

            nxt_r[j] = {
                mini.mini + h[j],
                (long long) h[j] * (i - j),
                i - j, i
            };
        }

        while (!greater.empty() && h[greater.back()] <= h[i]) {
            greater.pop_back();
        }

        if (!greater.empty()) {
            int j = greater.back();

            range mini = {0, 0, 0, j + 1};
            while (true) {
                range temp = combine(mini, nxt_r[mini.par]);
                if (temp.par == -1 || temp.par > i) {
                    break;
                }
                mini = temp;
            }

            nxt_l[i] = {
                mini.mini + h[i],
                (long long) h[i] * (i - j),
                i - j, j
            };
        }

        greater.push_back(i);
        less.push_back(i);
    }

    vector<long long> c(q);
    for (int i = 0; i < q; ++i) {
        range left = {0, 0, 0, l[i]};
        while (true) {
            range temp = combine(left, nxt_r[left.par]);
            if (temp.par == -1 || temp.par > r[i]) {
                break;
            }
            left = temp;
        }

        range right = {0, 0, 0, r[i]};
        while (true) {
            range temp = combine(right, nxt_l[right.par]);
            if (temp.par < l[i]) {
                break;
            }
            right = temp;
        }

        c[i] = min(
            left.mini + (long long) (r[i] - left.par + 1) * h[left.par],
            right.mini + (long long) (right.par - l[i] + 1) * h[right.par]
        );
    }

    return c;
}

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