Submission #733152

#	Time	Username	Problem	Language	Result	Execution time	Memory
733152		t6twotwo	Wiring (IOI17_wiring)	C++17	25 / 100	145 ms	33532 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct segment_tree {
    int n;
    vector<T> s;
    T (*f)(T, T);
    T e;
    segment_tree(int _n, T(*_f)(T, T), T _e) : f(_f), e(_e) {
        n = 2 << __lg(_n);
        s.resize(2 * n - 1, e);
    }
    void modify(int p, int l, int r, int x, T v) {
        if (r - l == 1) {
            s[p] = v;
            return;
        }
        int m = (l + r + 1) / 2;
        if (x < m) {
            modify(p * 2 + 1, l, m, x, v);
        } else {
            modify(p * 2 + 2, m, r, x, v);
        }
        s[p] = f(s[p * 2 + 1], s[p * 2 + 2]);
    }
    void modify(int x, T v) {
        modify(0, 0, n, x, v);
    }
    T range_query(int p, int l, int r, int L, int R) {
        if (R <= l || r <= L) {
            return e;
        }
        if (L <= l && r <= R) {
            return s[p];
        }
        int m = (l + r + 1) / 2;
        return f(range_query(p * 2 + 1, l, m, L, R), range_query(p * 2 + 2, m, r, L, R));
    }
    T range_query(int l, int r) {
        return range_query(0, 0, n, l, r);
    }
};
pair<ll, ll> fmin(pair<ll, ll> x, pair<ll, ll> y) {
    return {min(x.first, y.first), min(x.second, y.second)};
}
constexpr ll inf = 1E16;
long long min_total_length(vector<int> R, vector<int> B) {
    int N = R.size();
    int M = B.size();
    vector<array<int, 2>> T;
    for (int x : R) {
        T.push_back({x, 0});
    }
    for (int x : B) {
        T.push_back({x, 1});
    }
    sort(T.begin(), T.end());
    vector<ll> pfs(N + M + 1);
    for (int i = 0; i < N + M; i++) {
        pfs[i + 1] = pfs[i] + T[i][0];
    }
    vector<int> e(N + M, -1);
    for (int i = N + M - 2; i >= 0; i--) {
        if (T[i][1] == T[i + 1][1]) {
            e[i] = e[i + 1];
        } else {
            e[i] = i + 1;
        }
    }
    vector<int> d(N + M, -1);
    segment_tree<pair<ll, ll>> st(N + M, fmin, {inf, inf});
    vector<ll> dp(N + M + 1, inf);
    st.modify(0, {0, 0});
    dp[0] = 0;
    for (int i = 0; i < N + M; i++) {
        if (i > 0) {
            if (T[i][1] == T[i - 1][1]) {
                d[i] = d[i - 1];
            } else {
                d[i] = i - 1;
            }
        }
        if (d[i] != -1) {
            int j = d[i];
            dp[i + 1] = min(dp[i + 1], dp[j + 1] + (pfs[i + 1] - pfs[j + 1]) - 1LL * (i - j) * T[j][0]);
            int k = 2 * j + 1 - i;
            if (d[j] + 1 <= k) {
                dp[i + 1] = min(dp[i + 1], st.range_query(d[j] + 1, min(k, j) + 1).first + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j + 1][0]));
            }
            if (k < j) {
                dp[i + 1] = min(dp[i + 1], st.range_query(max(k, d[j]) + 1, j + 1).second + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j][0]));
            }
            if (e[i + 1] != -1) {
                st.modify(i + 1, {dp[i + 1] + pfs[i + 1] - 1LL * (i + 1) * T[e[i + 1]][0], dp[i + 1] + pfs[i + 1] - 1LL * (i + 1) * T[e[i + 1] - 1][0]});
            }
        }
    }
    return dp[N + M];
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45