제출 #588259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588259		farhan132	전선 연결 (IOI17_wiring)	C++17	100 / 100	149 ms	25956 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 2e5 + 5;

struct seg_tree{
	ll mx[4*N], n;
	void build(ll _n){
		n = _n;
		for(ll i = 0; i < 4*N; i++) mx[i] = 1e18;
	}
    void up(ll l, ll r, ll node, ll x, ll v){
    	if(r < x || l > x) return;
    	if(l == r){
    		mx[node] = min(v, mx[node]);
    		return;
    	}
    	ll m = (l + r)/2;
    	up(l, m, 2*node, x, v);
    	up(m+1,r,2*node + 1, x, v);
    	mx[node] = min(mx[2*node], mx[2*node + 1]);
    	return;
    }
    void up(ll x, ll v){
    	up(1,n,1,x,v);
    }
    ll get(ll l, ll r, ll node, ll x, ll y){
    	if(y < l || x > r) return 1e18;
    	if(x <= l && r <= y) return mx[node];
    	ll m = (l + r)/2;
    	return min(get(l, m, 2*node,x,y),get(m+1,r,2*node + 1,x,y));
    }
    ll get(ll x, ll y){
    	return get(1,n,1,x,y);
    }
}A,B,C;
ll dp[N], L[N], R[N];

ll pref[N];

ll sum(ll l, ll r){
	return pref[r] - pref[l - 1];
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector < ii > v;
	v.pb({0, 0});
	ll n = r.size();
	ll m = b.size();
	for(auto u : r){
		v.pb({u, 0});
	} 
	for(auto u : b){
		v.pb({u, 1});
	}
	sort(v.begin(), v.end());

	A.build(n + m);
	B.build(n + m);
	ll st[2] = {0, 0};
	pref[0] = 0; 
	for(ll i = 1; i <= n + m; i++){
		pref[i] = pref[i - 1] + v[i].ff;
		st[v[i].ss] = i;
		L[i] = st[v[i].ss^1] + 1;  
	}
	st[0] = st[1] = n + m + 1;
	for(ll i = n + m; i >= 1; i--){
		st[v[i].ss] = i;
		R[i] = st[v[i].ss^1] - 1; 
	}
	dp[n + m + 1] = 0;
	for(ll i = n + m; i >= 1; i--){
		if(R[i] == n + m){
			dp[i] = 1e18;
			A.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff);
			B.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff + (v[L[i]].ff - v[L[i] - 1].ff)*(i - L[i] + 1));
			continue;
		}
		ll x = R[i];
		ll l = L[x + 1];
		ll r = R[x + 1];
		ll gap = v[l].ff - v[x].ff;
		ll mx = x - i + 1;
		ll S = mx * v[x].ff - sum(i, x);
		dp[i] = 1e18;
		// A
		dp[i] = min(dp[i], S + gap * mx + A.get(l, min(r, l + mx - 1)));
		// B
		if(l + mx <= r) dp[i] = min(dp[i], S + B.get(l + mx, r));
		// mixed 
		if(l == r) dp[i] = min(dp[i], S + gap * mx + dp[l]);
		//updates
		// A
		A.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff);
		// B
		B.up(i, dp[i + 1] + sum(L[i], i) - (i - L[i] + 1)*v[L[i]].ff + (v[L[i]].ff - v[L[i] - 1].ff)*(i - L[i] + 1));

	}

	return dp[1];
}

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