Submission #797683

#	Time	Username	Problem	Language	Result	Execution time	Memory
797683		PixelCat	Wiring (IOI17_wiring)	C++14	100 / 100	79 ms	12884 KiB

wiring

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "wiring.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using i32 = int32_t;
using pii = pair<int, int>;

// int solve_13(const vector<i32> &v1, const vector<i32> &v2) {
//     int sl = 0, sr = 0;
//     for(auto &i:v1) sl += i;
//     sl += max(0ll, sz(v2) - sz(v1)) * v1.back();
//     for(auto &i:v2) sr += i;
//     sr += max(0ll, sz(v1) - sz(v2)) * v2.front();
//     return sr - sl;
// }

// int cost(const vector<pii> &v, int l, int r) {
//     vector<i32> vl, vr;
//     For(i, l, r) {
//         if(v[i].S == v[l].S) vl.eb(v[i].F);
//         else vr.eb(v[i].F);
//     }
//     return solve_13(vl, vr);
// }

// const int MAXN = 100'000;
const int MAXN = 200'000;
const int MAXND = MAXN * 4;
const int INF = 4e18;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int add[MAXND + 10];
    int mn[MAXND + 10];
    void pull(int id) {
        mn[id] = min(mn[L(id)], mn[R(id)]) + add[id];
    }
    void build(int id, int l, int r) {
        add[id] = 0;
        mn[id] = INF;
        if(l == r) return;
        int m = (l + r) / 2;
        build(L(id), l, m);
        build(R(id), m + 1, r);
    }
    void single_upd(int id, int l, int r, int pos, int val) {
        if(l == r) {
            mn[id] = val;
            return;
        }
        int m = (l + r) / 2;
        if(pos <= m) single_upd(L(id), l, m, pos, val);
        else single_upd(R(id), m + 1, r, pos, val);
        pull(id);
    }
    void range_add(int id, int l, int r, int L, int R, int val) {
        if(l >= L && r <= R) {
            add[id] += val;
            mn[id] += val;
            return;
        }
        int m = (l + r) / 2;
        if(L <= m) range_add(L(id), l, m, L, R, val);
        if(R > m)  range_add(R(id), m + 1, r, L, R, val);
        pull(id);
    }
    int qry() {
        return mn[0];
    }
    void out(int id, int l, int r, int tot) {
        if(l == r) {
            cerr << " " << (tot + mn[id]);
            return;
        }
        tot += add[id];
        int m = (l + r) / 2;
        out(L(id), l, m, tot);
        out(R(id), m + 1, r, tot);
    }
} seg;

// struct NotSegTree {
//     int a[MAXN + 10];
//     void build(int id, int l, int r) {
//         fill(a, a + MAXN + 10, INF);
//     }
//     void single_upd(int id, int l, int r, int pos, int val) {
//         a[pos] = val;
//     }
//     void range_add(int id, int l, int r, int L, int R, int val) {
//         For(i, L, R) a[i] += val;
//     }
//     int qry() {
//         int ans = INF;
//         For(i, 0, MAXN + 9) ans = min(ans, a[i]);
//         return ans;
//     }
// } seg;

int dp[MAXN + 10];

int min_total_length(vector<int32_t> r, vector<int32_t> b) {
    int n = sz(r), m = sz(b);
    assert(max(n, m) <= MAXN);

    vector<pii> v;  // pos, color
    v.eb(-1, -1);
    for(auto &i:r) v.eb(i, 0);
    for(auto &i:b) v.eb(i, 1);
    sort(all(v));

    dp[0] = 0;
    int l1, r1, l2;
    int r2 = 1;
    while(v[r2].S == v[1].S) {
        dp[r2] = INF;
        r2++;
    }
    l1 = r1 = 0; l2 = 1;
    for(; r2 <= n + m; r2++) {
        if(v[r2].S != v[r2 - 1].S) {
            l1 = l2; r1 = r2 - 1; l2 = r2;
            seg.build(0, l1, r1);
            int tot = 0;
            Forr(i, r1, l1) {
                tot += v[r2].F - v[i].F;
                seg.single_upd(0, l1, r1, i, min(dp[i], dp[i - 1]) + tot);
            }
        } else {
            int p = r1 - (r2 - l2);
            if(p >= l1) {
                seg.range_add(0, l1, r1, l1, p, v[r2].F - v[l2].F);
                seg.range_add(0, l1, r1, p + 1, r1, v[r2].F - v[r1].F);
            } else {
                seg.range_add(0, l1, r1, l1, r1, v[r2].F - v[r1].F);
            }
        }
        dp[r2] = seg.qry();

        // For(i, l1, r1) {
        //     assert(cost(v, i, r2) + min(dp[i], dp[i - 1]) == seg.a[i]);
        // }

        // cerr << r2 << " " << dp[r2] << "\n";
        // cerr << r2 << ":";
        // seg.out(0, l1, r1, 0);
        // cerr << "\n";
        // For(j, l1, r1) {
        //     dp[r2] = min({dp[r2], dp[j - 1] + cost(v, j, r2), dp[j] + cost(v, j, r2)});
        // }
        // cerr << l1 << " " << r1 << " " << l2 << " " << r2 << "\n";
    }
    return dp[n + m];
}

// #ifdef NYAOWO
// void run_test(i32 n, i32 m) {
//     i32 lim = 100;
//     mt19937 rng(time(NULL));
//     set<i32> st;
//     vector<i32> v1, v2;
//     For(i, 1, n) {
//         v1.eb(rng() % lim);
//         while(st.count(v1.back())) {
//             v1.back() = rng() % lim;
//         }
//         st.insert(v1.back());
//     }
//     For(i, 1, m) {
//         v2.eb(rng() % lim);
//         while(st.count(v2.back())) {
//             v2.back() = rng() % lim;
//         }
//         st.insert(v2.back());
//     }
//     sort(all(v1));
//     sort(all(v2));
//     ignore = min_total_length(v1, v2);
// }

// int32_t main() {
//     For(_, 1, 10000) {
//         run_test(10, 1);
//     }
// }
// #endif

/*

4 5
1 2 3 7
0 4 5 9 10

10

*/

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