Submission #422052

#	Time	Username	Problem	Language	Result	Execution time	Memory
422052		timmyfeng	Meetings (IOI18_meetings)	C++17	100 / 100	3615 ms	488068 KiB

meetings

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

#include "meetings.h"

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

struct segtree {
    segtree *left = nullptr, *right = nullptr;
    long long lazy_m = -1, lazy_b = 0, first = 0, last = 0;

    void apply(long long m, long long b, int l, int r) {
        if (m == -1) {
            first += b;
            last += b;
            lazy_b += b;
        } else {
            first = m * l + b;
            last = m * r + b;
            lazy_m = m;
            lazy_b = b;
        }
    }

    void push(int l, int r) {
        if (!left) {
            left = new segtree();
            right = new segtree();
        }

        int m = (l + r) / 2;
        left->apply(lazy_m, lazy_b, l, m);
        right->apply(lazy_m, lazy_b, m + 1, r);
        lazy_m = -1, lazy_b = 0;
    }

    void pull() {
        first = left->first;
        last = right->last;
    }

    long long query(int a, int l, int r) {
        if (l == r) {
            return first;
        } else {
            push(l, r);
            int m = (l + r) / 2;
            if (a <= m) {
                return left->query(a, l, m);
            } else {
                return right->query(a, m + 1, r);
            }
        }
    }

    void update(int a, int b, long long x, long long y, long long z, int l, int r) {
        if (b < l || r < a) {
            return;
        } else if (a <= l && r <= b) {
            if (first + x <= y * l + z) {
                apply(-1, x, l, r);
                return;
            } else if (last + x >= y * r + z) {
                apply(y, z, l, r);
                return;
            }
        }

        push(l, r);
        int m = (l + r) / 2;
        left->update(a, b, x, y, z, l, m);
        right->update(a, b, x, y, z, m + 1, r);
        pull();
    }
};

int adj[N][2], first[N], last[N], n;
vector<array<int, 3>> queries[N];
array<int, 2> sparse[L][N];
long long cost[N], ans[N];
vector<int> h;
segtree *mini;

void dfs(int u) {
    for (auto c : adj[u]) {
        if (c != -1) {
            dfs(c);
        }
    }

    long long maxi = h[u];
    for (auto [l, r, i] : queries[u]) {
        ans[i] = min(ans[i], (u - l + 1) * maxi +
            (r == u ? 0 : mini->query(r, 0, n - 1)));
    }

    first[u] = adj[u][0] == -1 ? u : first[adj[u][0]];
    last[u] = adj[u][1] == -1 ? u : last[adj[u][1]];

    mini->update(u, last[u], (u - first[u] + 1) * maxi,
        maxi, (adj[u][0] == -1 ? 0 : mini->query(u - 1, 0, n - 1)) - (u - 1) * maxi, 0, n - 1);
}

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

    fill(ans, ans + q, LLONG_MAX);

    for (int z = 0; z < 2; ++z) {
        ::h = h;
        fill(queries, queries + n, vector<array<int, 3>>());
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                adj[i][j] = -1;
            }
        }

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

            if (!stk.empty()) {
                int j = stk.back();
                adj[i][0] = adj[j][1];
                adj[j][1] = i;
            } else {
                adj[i][0] = root;
                root = i;
            }

            stk.push_back(i);
        }

        for (int i = 0; i <= __lg(n); ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                if (i == 0) {
                    sparse[i][j] = {h[j], -j};
                } else {
                    sparse[i][j] = max(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
                }
            }
        }

        for (int i = 0; i < q; ++i) {
            int k = __lg(r[i] - l[i] + 1);
            auto [y, j] = max(sparse[k][l[i]], sparse[k][r[i] - (1 << k) + 1]);
            queries[-j].push_back({l[i], r[i], i});
        }

        mini = new segtree();
        dfs(root);

        reverse(h.begin(), h.end());
        for (int i = 0; i < q; ++i) {
            int temp = l[i];
            l[i] = n - 1 - r[i];
            r[i] = n - 1 - temp;
        }
    }

    return vector<long long>(ans, ans + q);
}

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