Submission #997830

#	Time	Username	Problem	Language	Result	Execution time	Memory
997830		biank	Meetings (IOI18_meetings)	C++14	45 / 100	2136 ms	786432 KiB

meetings

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())

using ll = long long;

template<typename T>
void chmin(T &x, T v) {
    if (x > v) x = v;
}

const int MAX_H = 21;
const int INF = 1e9;

struct Node {
    int cost[MAX_H][MAX_H];
    int pref[MAX_H], suff[MAX_H];
    int maxh;
    bool neutr;
    Node(int v = 0) {
        neutr = true;
        for (int h1 = 0; h1 < MAX_H; h1++) {
            for (int h2 = 0; h2 < MAX_H; h2++) {
                cost[h1][h2] = INF;
            }
        }
        for (int h = 0; h < MAX_H; h++) {
            pref[h] = suff[h] = INF;
        }
        if (v != 0) {
            neutr = false;
            cost[v][v] = maxh = v;
            for (int h = 0; h < MAX_H; h++) {
                pref[h] = suff[h] = max(h, v);
            }
        }
    }
    int best() {
        int ans = INF;
        for (int h1 = 0; h1 < MAX_H; h1++) {
            for (int h2 = 0; h2 < MAX_H; h2++) {
                chmin(ans, cost[h1][h2]);
            }
        }
        return ans;
    }
    friend Node op(const Node &a, const Node &b) {
        if (a.neutr) return b;
        if (b.neutr) return a;
        Node c;
        for (int h1 = 0; h1 < MAX_H; h1++) {
            for (int h2 = 0; h2 < MAX_H; h2++) {
                chmin(c.cost[h1][max(h2, b.maxh)], a.cost[h1][h2] + b.pref[h2]);
                chmin(c.cost[max(h1, a.maxh)][h2], a.suff[h1] + b.cost[h1][h2]);
            }
        }
        for (int h = 0; h < MAX_H; h++) {
            c.suff[h] = a.suff[max(h, b.maxh)] + b.suff[h];
            c.pref[h] = a.pref[h] + b.pref[max(h, a.maxh)];
        }
        c.maxh = max(a.maxh, b.maxh);
        c.neutr = false;
        return c;
    }
};

const int SZ = 1 << 17;

Node st[2 * SZ];

void init(vector<int> &H) {
    for (int i = 0; i < sz(H); i++) {
        st[i + SZ] = H[i];
    }
    for (int i = SZ - 1; i > 0; i--) {
        st[i] = op(st[2 * i], st[2 * i + 1]);
    }
}


Node query(int l, int r) {
    l += SZ, r += SZ;
    Node leftRes, rightRes;
    while (l <= r) {
        if (l % 2 == 1) leftRes = op(leftRes, st[l++]);
        if (r % 2 == 0) rightRes = op(st[r--], rightRes);
        l /= 2, r /= 2;
    }
    return op(leftRes, rightRes);
}

vector<ll> brute(vector<int> H, vector<int> L, vector<int> R) {
    int N = sz(H), Q = sz(L);
    vector<vector<int>> val(N, vector<int>(N));
    vector<vector<ll>> pref(N, vector<ll>(N + 1));
    for (int x = 0; x < N; x++) {
        val[x][x] = H[x];
        for (int y = x + 1; y < N; y++) {
            val[x][y] = max(H[y], val[x][y - 1]);
        }
        for (int y = x - 1; y >= 0; y--) {
            val[x][y] = max(H[y], val[x][y + 1]);
        }
        pref[x][0] = 0LL;
        for (int i = 0; i < N; i++) {
            pref[x][i + 1] = pref[x][i] + val[x][i];
        }
    }
    vector<ll> ans(Q, 1e18);
    for (int i = 0; i < Q; i++) {
        for (int x = L[i]; x <= R[i]; x++) {
            chmin(ans[i], pref[x][R[i] + 1] - pref[x][L[i]]);
        }
    }
    return ans;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = sz(H), Q = sz(L);
    if (N <= 5000 && Q <= 5000) {
        return brute(H, L, R);
    }
    init(H);
    vector<ll> ans(Q, INF);
    for (int i = 0; i < Q; i++) {
        Node res = query(L[i], R[i]);
        ans[i] = res.best();
    }
    return ans;
}

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