Submission #81145

#	Time	Username	Problem	Language	Result	Execution time	Memory
81145		polyfish	Wiring (IOI17_wiring)	C++14	13 / 100	252 ms	40496 KiB

wiring

//pantyhose(black) + glasses = infinity

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int64_t INF = 1e18;
const int MAX_N = 200002;

struct segment_tree {
    int n;
    vector<int64_t> st;

    segment_tree(int _n) {
        n = _n;
        st.resize(4*n, INF);
    }

    void upd(int pos, int64_t val, int l, int r, int id) {
        if (pos<l || pos>r)
            return;
        if (pos==l && r==pos) {
            st[id] = min(st[id], val);
            return;
        }
        int mid = (l + r) / 2;
        upd(pos, val, l, mid, id*2);
        upd(pos, val, mid+1, r, id*2+1);
        st[id] = min(st[id*2], st[id*2+1]);
    }

    int64_t get(int u, int v, int l, int r, int id) {
        if (v<l || u>r)
            return INF;
        if (u<=l && r<=v)
            return st[id];
        int mid = (l + r) / 2;
        return min(get(u, v, l, mid, id*2),
                   get(u, v, mid+1, r, id*2+1));
    }

    void upd(int pos, int64_t val) {
        upd(pos, val, 1, n, 1);
    }

    int64_t get(int u, int v) {
        if (u>v)
            return INF;
        return get(u, v, 1, n, 1);
    }
};

vector<pair<int, int> > all;
int n, _prev[MAX_N], _next[MAX_N];
int64_t ps[MAX_N], f[MAX_N];

void init(vector<int> r, vector<int> b) {
    for (auto v : r)
        all.push_back(make_pair(v, 1));
    for (auto v : b)
        all.push_back(make_pair(v, 0));
    sort(all.begin(), all.end());
    n = all.size() - 1;
    for (int i=1; i<=n; ++i) {
        ps[i] = ps[i-1] + all[i].first;
    }
    _prev[1] = 1;
    for (int i=2; i<=n; ++i) {
        if (all[i].second==all[i-1].second)
            _prev[i] = _prev[i-1];
        else
            _prev[i] = i;
    }
    _next[n] = n;
    for (int i=n-1; i>=1; --i) {
        if (all[i].second==all[i+1].second)
            _next[i] = _next[i+1];
        else
            _next[i] = i;
    }
}

int64_t min_total_length(vector<int> r, vector<int> b) {
    all.resize(1);
    init(r, b);
    for (int i=1; i<=n; ++i)
        f[i] = INF;
    segment_tree tree1(n), tree2(n);
    tree1.upd(1, f[0] - all[_next[1]].first);
    tree2.upd(1, f[0] - all[_next[1]+1].first);
    for (int i=_next[1]+1; i<=n; ++i) {
        int l = max(_prev[_prev[i]-1], 2*_prev[i]-i-1);
        int r = _prev[i]-1;
        f[i] = tree1.get(l, r) + ps[i] - 2*ps[_prev[i]-1] - (int64_t)(i - 2*_prev[i]+1)*all[_prev[i]-1].first;
        //cerr << ps[i] - 2*ps[_prev[i]-1] - 1LL*(i + 2*_prev[i]+1)*all[_prev[i]-1].first << '\n';
        //debug(tree1.get(l, r));
        l = _prev[_prev[i]-1];
        r = min(_prev[i]-1, 2*_prev[i]-i-1);
        f[i] = min(f[i], tree2.get(l, r) + ps[i] - 2*ps[_prev[i]-1] + (int64_t)(2*_prev[i]-i-1)*all[_prev[i]].first);
        if (_next[i]!=n) {
            tree1.upd(i+1, f[i] + ps[i] - 1LL * (i+1) * all[_next[i+1]].first);
            tree2.upd(i+1, f[i] + ps[i] - 1LL * (i+1) * all[_next[i+1]+1].first);
        }
    }
    return f[n];
}

//int main() {
//	#ifdef GLASSES_GIRL
//		freopen(FILE_NAME".inp", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
//	#endif
//	ios::sync_with_stdio(0); cin.tie(0);
//	int m, n;
//	cin >> m >> n;
//    vector<int> r(m), b(n);
//    for (int i=0; i<m; ++i)
//        cin >> r[i];
//    for (int i=0; i<n; ++i)
//        cin >> b[i];
//    cout << min_total_length(r, b);
//}

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