Submission #197074

#	Time	Username	Problem	Language	Result	Execution time	Memory
197074		popovicirobert	Wiring (IOI17_wiring)	C++14	100 / 100	223 ms	22764 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

static const ll INF = 1e18;

struct Node {
    ll mn;
    Node(ll _mn = INF) : mn(_mn) { }
};

class SegTree {
public:

    vector <Node> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 5);
    }

    inline void update(int l, int r, Node cur) { // l == r ???
        update(1, 0, n, l, r, cur);
    }

    inline Node query(int l, int r) {
        return query(1, 0, n, l, r);
    }

private:

    inline Node combine(Node a, Node b) {
        return Node(min(a.mn, b.mn));
    }

    void update(int nod, int left, int right, int l, int r, Node cur) {
        if(l <= left && right <= r) {
            aint[nod] = combine(aint[nod], cur);
            return ;
        }
        int mid = (left + right) / 2;

        if(l <= mid) update(2 * nod, left, mid, l, r, cur);
        if(mid < r) update(2 * nod + 1, mid + 1, right, l, r, cur);

        aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
    }

    Node query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        int mid = (left + right) / 2;
        Node ans(INF);

        if(l <= mid) ans = combine(ans, query(2 * nod, left, mid, l, r));
        if(mid < r) ans = combine(ans, query(2 * nod + 1, mid + 1, right, l, r));

        return ans;
    }
};

ll min_total_length(vector<int> r, vector<int> b) {
    vector < pair <int, int> > x(1);
    for(auto it : r) {
        x.push_back({it, 0});
    }
    for(auto it : b) {
        x.push_back({it, 1});
    }
    sort(x.begin(), x.end());

    int i, n = r.size() + b.size();
    vector <int> last(n + 1, 0), nxt(n + 2, n + 1);
    vector <ll> sp(n + 1);

    for(i = 1; i <= n; i++) {
        last[i] = ((x[i].second ^ x[i - 1].second) ? i - 1 : last[i - 1]);
        sp[i] = sp[i - 1] + x[i].first;
        //cerr << x[i].first << " ";
    }
    for(i = n; i >= 1; i--) {
        nxt[i] = ((x[i].second ^ x[i + 1].second) ? i + 1 : nxt[i + 1]);
    }

    SegTree st1, st2; st1.init(n), st2.init(n);
    vector <ll> dp(n + 1);

    for(i = 1; i <= n; i++) {
        st1.update(i - 1, i - 1, Node(dp[i - 1] - 1LL * (i - 1) * x[nxt[i] - 1].first + sp[i - 1]));
        st2.update(i - 1, i - 1, Node(dp[i - 1] - 1LL * (i - 1) * x[nxt[i] - 1].first + sp[i - 1]
                                      + 1LL * (nxt[i] - i) * (x[nxt[i]].first - x[nxt[i] - 1].first)));

        if(last[i] == 0) { dp[i] = INF; continue; }

        int a = last[i] - last[last[i]], b = i - last[i];
        ll cur = sp[i] - sp[last[i]] - 1LL * (i - last[i]) * x[last[i] + 1].first - sp[last[i]] + 1LL * x[last[i]].first * last[i];

        dp[i] = cur + 1LL * (i - last[i]) * (x[last[i] + 1].first - x[last[i]].first) + st1.query(max(0, last[i] - b), last[i] - 1).mn;
        if(a > b) {
            dp[i] = min(dp[i], cur + st2.query(last[last[i]], last[i] - b).mn);
        }

        if(a == 1) {
            dp[i] = min(dp[last[i]] + sp[i] - sp[last[i]] - 1LL * x[last[i]].first * b, dp[i]);
        }

    }

    return dp[n];
}

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