Submission #904330

#	Time	Username	Problem	Language	Result	Execution time	Memory
904330		aqxa	Wiring (IOI17_wiring)	C++17	100 / 100	122 ms	14404 KiB

wiring

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

const ll inf = 1e18; 

#include "wiring.h"

struct segtree {
    struct node {
        long long add = 0; 
        long long mv = 0; 
        void apply(int l, int r, long long x) {
            add += x; 
			mv += x; 
        } 
    }; 

    node unite(const node & x, const node & y) const {
        node res; 
        res.mv = min(x.mv, y.mv); 
        return res; 
    }

    inline void push(int x, int l, int r) {
        int y = (l + r) >> 1; 
        int z = x + ((y - l + 1) << 1);
        if (tree[x].add != 0) {
            tree[x + 1].apply(l, y, tree[x].add);
            tree[z].apply(y + 1, r, tree[x].add);
            tree[x].add = 0; 
        }
    }

    inline void pull(int x, int z) {
        tree[x] = unite(tree[x + 1], tree[z]);
    }

    int n; 
    vector<node> tree; 

    void build(int x, int l, int r) {
        if (l == r) {
            return;
        }
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        build(x + 1, l, y);
        build(z, y + 1, r);
        pull(x, z);
    }

    template <typename M>
    void build(int x, int l, int r, const vector<M> &v) {
        if (l == r) {
            tree[x].apply(l, r, v[l]);
            return;
        }
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        build(x + 1, l, y, v);
        build(z, y + 1, r, v);
        pull(x, z);
    }

    node get(int x, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return tree[x];
        }
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        push(x, l, r);
        node res{};
        if (R <= y) {
            res = get(x + 1, l, y, L, R);
        } else {
            if (L > y) {
                res = get(z, y + 1, r, L, R);
            } else {
                res = unite(get(x + 1, l, y, L, R), get(z, y + 1, r, L, R));
            }
        }
        pull(x, z);
        return res;
    }

    template <typename... M>
    void modify(int x, int l, int r, int L, int R, const M&... v) {
        if (L <= l && r <= R) {
            tree[x].apply(l, r, v...);
            return;
        }
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        push(x, l, r);
        if (L <= y) {
            modify(x + 1, l, y, L, R, v...);
        }
        if (R > y) {
            modify(z, y + 1, r, L, R, v...);
        }
        pull(x, z);
    }

    int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
        if (l == r) {
            return l;
        }
        push(x, l, r);
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        int res;
        if (f(tree[x + 1])) {
            res = find_first_knowingly(x + 1, l, y, f);
        } else {
            res = find_first_knowingly(z, y + 1, r, f);
        }
        pull(x, z);
        return res;
    }

    int find_first(int x, int l, int r, int L, int R, const function<bool(const node&)> &f) {
        if (L <= l && r <= R) {
            if (!f(tree[x])) {
                return -1;
            }
            return find_first_knowingly(x, l, r, f);
        }
        push(x, l, r);
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        int res = -1;
        if (L <= y) {
            res = find_first(x + 1, l, y, L, R, f);
        }
        if (R > y && res == -1) {
            res = find_first(z, y + 1, r, L, R, f);
        }
        pull(x, z);
        return res;
    }

    int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
        if (l == r) {
            return l;
        }
        push(x, l, r);
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        int res;
        if (f(tree[z])) {
            res = find_last_knowingly(z, y + 1, r, f);
        } else {
            res = find_last_knowingly(x + 1, l, y, f);
        }
        pull(x, z);
        return res;
    }

    int find_last(int x, int l, int r, int L, int R, const function<bool(const node&)> &f) {
        if (L <= l && r <= R) {
            if (!f(tree[x])) {
                return -1;
            }
            return find_last_knowingly(x, l, r, f);
        }
        push(x, l, r);
        int y = (l + r) >> 1;
        int z = x + ((y - l + 1) << 1);
        int res = -1;
        if (R > y) {
            res = find_last(z, y + 1, r, L, R, f);
        }
        if (L <= y && res == -1) {
            res = find_last(x + 1, l, y, L, R, f);
        }
        pull(x, z);
        return res;
    }

    segtree(int _n) {
        n = _n;
        tree.resize(2 * n - 1);
        build(0, 0, n - 1);
    }

    template <typename M>
    segtree(const vector<M> &v) {
        n = v.size();
        tree.resize(2 * n - 1);
        build(0, 0, n - 1, v);
    }

    node get(int L, int R) {
        assert(0 <= L && L <= R && R <= n - 1);
        return get(0, 0, n - 1, L, R);
    }

    template <typename... M>
    void modify(int L, int R, const M&... v) {
        assert(0 <= L && L <= R && R <= n - 1);
        modify(0, 0, n - 1, L, R, v...);
    }
    // find_first and find_last call all FALSE elements
    // to the left (right) of the sought position exactly once

    int find_first(int L, int R, const function<bool(const node&)> &f) {
        assert(0 <= L && L <= R && R <= n - 1);
        return find_first(0, 0, n - 1, L, R, f);
    }

    int find_last(int L, int R, const function<bool(const node&)> &f) {
        assert(0 <= L && L <= R && R <= n - 1);
        return find_last(0, 0, n - 1, L, R, f);
    }
};

long long min_total_length(std::vector<int> a, std::vector<int> b) {
	vector<array<int, 2>> f; 
	for (auto x: a) f.push_back({x, 0}); 
	for (auto x: b) f.push_back({x, 1}); 
	sort(f.begin(), f.end()); 
	int cc = f[0][1] ^ 1; 
	
	vector<vector<ll>> segs; 
	for (auto [x, v]: f) {
		if (v == cc) {
			segs.back().push_back(x); 
		} else {
			segs.push_back({(ll)x}); 
			cc ^= 1; 
		}
	}	

	vector<ll> dp(segs[0].size() + 1, inf); 
	dp[0] = 0; 

	for (int i = 1; i < segs.size(); ++i) {
		vector<ll> a = segs[i - 1], b = segs[i]; 
		int n = a.size(), m = b.size(); 
		ll A = a.back(), B = b[0]; 
		
		segtree st(n); 

		ll sa = 0, cnt = 0; 
		for (int j = n - 1; j >= 0; --j) {
			dp[j] = min(dp[j], dp[j + 1]); 
			sa += a[j]; 
			cnt++; 
			st.modify(j, j, dp[j] + cnt * B - sa); 
			// st[j] = dp[j] + cnt * B - sa; 
		} 
		
		vector<ll> ans(m + 1, inf); 
		ans[0] = dp[n]; 
		// ans[1] = min on st 
		ans[1] = st.get(0, n - 1).mv; 
		for (int j = 2; j <= m; ++j) {
            // cout << "before " << j << '\n';
            // for (int k = 0; k < n; ++k) cout << st.get(k, k).mv << " \n"[k == n - 1]; 
			if (n - j >= 0) {
                // cout << 0 << ' ' << n - j << ' ' << b[j] - B << '\n';
				st.modify(0, min(n - j, n - 1), b[j - 1] - B); 
			}
			if (n - j < n - 1) {
                // cout << n - j + 1 << ' ' << n - 1 << ' ' << b[j] - A << '\n';
				st.modify(max(n - j + 1, 0), n - 1, b[j - 1] - A); 
			}
			// s.x += b[j] - B for x <= n - j
			// s.x += b[j] - A for x > n - j 

			// ans[j] = min on st 
			ans[j] = min(st.get(0, n - 1).mv, ans[j]); 
            // cout << "!!! " << j << ' ' << ans[j] << '\n';
		}
		dp = ans; 
        // for (auto x: dp) cout << x << ' '; 
        // cout << '\n';
	}

	return dp.back();
}


// int main() {
// 	ios_base::sync_with_stdio(false); 
// 	cin.tie(0); 
	
//     int tt; 
//     cin >> tt; 
//     for (int t = 0; t < tt; ++t) {
//         int n, m;
//         cin >> n >> m; 
//         vector<int> a(n); 
//         for (auto & x: a) cin >> x; 
//         vector<int> b(m); 
//         for (auto & x: b) cin >> x; 
//         sort(a.begin(), a.end()); 
//         sort(b.begin(), b.end()); 
//         cout << "!!! \n" << min_total_length(a, b) << "\n";        
//     }

// 	return 0;
// }

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:239:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |  for (int i = 1; i < segs.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~

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