Submission #421380

#	Time	Username	Problem	Language	Result	Execution time	Memory
421380		timmyfeng	Meetings (IOI18_meetings)	C++17	0 / 100	91 ms	7080 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[L][N], nxt_r[L][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
        };
    }
}

void calc(int k, int i) {
    if (nxt_r[k][i].par != -1 || k == 0) {
        return;
    }

    calc(k - 1, i);
    int p = nxt_r[k - 1][i].par;
    if (p != -1) {
        calc(k - 1, p);
        nxt_r[k][i] = combine(nxt_r[k - 1][i], nxt_r[k - 1][p]);
    }
}

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 <= __lg(n); ++i) {
        for (int j = 0; j < n; ++j) {
            nxt_l[i][j].par = nxt_r[i][j].par = -1;
        }
    }

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

            range mini = {0, 0, 0, i - 1};
            for (int k = __lg(n); k >= 0; --k) {
                int p = nxt_l[k][mini.par].par;
                if (p >= j) {
                    mini = combine(mini, nxt_l[k][mini.par]);
                }
            }

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

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

            range mini = {0, 0, 0, j + 1};
            for (int k = __lg(n); k >= 0; --k) {
                calc(k, mini.par);
                int p = nxt_r[k][mini.par].par;
                if (p != -1 && p <= i) {
                    mini = combine(mini, nxt_r[k][mini.par]);
                }
            }

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

            for (int k = 1; k <= __lg(n); ++k) {
                int p = nxt_l[k - 1][i].par;
                if (p != -1) {
                    nxt_l[k][i] = combine(nxt_l[k - 1][i], nxt_l[k - 1][p]);
                }
            }
        }
        stk.push_back(i);
    }

    vector<long long> c(q);
    for (int i = 0; i < q; ++i) {
        range left = {0, 0, 0, l[i]};
        for (int k = __lg(n); k >= 0; --k) {
            calc(k, left.par);
            int p = nxt_r[k][left.par].par;
            if (p != -1 && p <= r[i]) {
                left = combine(left, nxt_r[k][left.par]);
            }
        }

        range right = {0, 0, 0, r[i]};
        for (int k = __lg(n); k >= 0; --k) {
            int p = nxt_l[k][right.par].par;
            if (p >= l[i]) {
                right = combine(right, nxt_l[k][right.par]);
            }
        }

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

    return c;
}

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