Submission #421333

#	Time	Username	Problem	Language	Result	Execution time	Memory
421333		timmyfeng	Meetings (IOI18_meetings)	C++17	0 / 100	52 ms	6228 KiB

meetings

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

#include "meetings.h"

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

long long mini_l[L][N], mini_r[L][N], sum_l[L][N], sum_r[L][N];
int par_l[L][N], par_r[L][N];
vector<int> h;

void calc(int i, int l) {
    if (par_r[i][l] != -1 || i == 0) {
        return;
    }

    calc(i - 1, l);
    int p = par_r[i - 1][l];

    if (p == -1) {
        return;
    }

    calc(i - 1, p);
    par_r[i][l] = par_r[i - 1][p];
    sum_r[i][l] = sum_r[i - 1][l] + sum_r[i - 1][p];
    mini_r[i][l] = min(
        (long long) h[p] * (p - l) + mini_r[i - 1][p],
        mini_r[i - 1][l] + sum_r[i - 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) {
            par_l[i][j] = par_r[i][j] = -1;
            sum_l[i][j] = sum_r[i][j] = 0;
            mini_l[i][j] = mini_r[i][j] = 0;
        }
    }

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

            int u = r - 1;
            long long mini = 0;
            for (int i = __lg(n); i >= 0; --i) {
                if (par_l[i][u] >= l) {
                    mini = min(
                        (long long) h[u] * (r - 1 - u) + mini_l[i][u],
                        mini + sum_l[i][u]
                    );
                    u = par_l[i][u];
                }
            }
            mini += h[l];

            par_r[0][l] = r;
            mini_r[0][l] = mini;
            sum_r[0][l] = (long long) h[l] * (r - l);
        }

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

            int u = l + 1;
            long long mini = 0;
            for (int i = __lg(n); i >= 0; --i) {
                calc(i, u);
                if (par_r[i][u] != -1) {
                    mini = min(
                        (long long) h[u] * (u - l - 1) + mini_r[i][u],
                        mini + sum_r[i][u]
                    );
                    u = par_r[i][u];
                }
            }
            mini += h[r];

            par_l[0][r] = l;
            mini_l[0][r] = mini;
            sum_l[0][r] = (long long) h[r] * (r - l);

            for (int i = 1; i <= __lg(n); ++i) {
                int p = par_l[i - 1][r];
                if (p != -1) {
                    par_l[i][r] = par_l[i - 1][p];
                    sum_l[i][r] = sum_l[i - 1][r] + sum_l[i - 1][p];
                    mini_l[i][r] = min(
                        (long long) h[p] * (r - p) + mini_l[i - 1][p],
                        mini_l[i - 1][r] + sum_l[i - 1][p]
                    );
                }
            }
        }
        stk.push_back(r);
    }

    vector<long long> c(q);
    for (int i = 0; i < q; ++i) {
        int u = l[i];
        long long left = 0;
        for (int j = __lg(n); j >= 0; --j) {
            calc(j, u);
            int p = par_r[j][u];
            if (p != -1 && p <= r[i]) {
                left = min(
                    (long long) h[u] * (u - l[i]) + mini_r[j][u],
                    left + sum_r[j][u]
                );
                u = p;
            }
        }
        left += (long long) (r[i] - u + 1) * h[u];

        u = r[i];
        long long right = 0;
        for (int j = __lg(n); j >= 0; --j) {
            int p = par_l[j][u];
            if (p >= l[i]) {
                right = min(
                    (long long) h[u] * (r[i] - u) + mini_l[j][u],
                    right + sum_l[j][u]
                );
                u = p;
            }
        }
        right += (long long) (u - l[i] + 1) * h[u];

        c[i] = min(left, right);
    }

    return c;
}

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