Submission #761282

#	Time	Username	Problem	Language	Result	Execution time	Memory
761282		minhcool	Wiring (IOI17_wiring)	C++17	100 / 100	127 ms	35296 KiB

wiring

//#define local
#ifndef local
#include "wiring.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

/*200 200
2529 2576 2582 2586 2658 2714 2729 2737 2777 2831 2843 2845 2868 2882 2911 2943 3037 3038 3065 3075 3096 3125 3147 3158 3167 3200 3219 3241 3260 3272 3273 3295 3342 3347 3371 3377 3495 3684 3763 3826 3831 3866 3880 3903 3913 3980 4000 4029 4067 4162 4210 4265 4322 4330 4355 4434 4454 4490 4493 4509 4541 4553 4563 4586 4588 4629 4635 4664 4686 4719 4737 4769 4772 4775 4781 4785 4880 4975 5017 5022 5061 5100 5138 5163 5200 5223 5233 5296 5337 5421 5465 5471 5513 5521 5542 5579 5592 5596 5782 5800 5904 5914 5985 6000 6029 6050 6081 6088 6094 6151 6158 6168 6200 6208 6224 6277 6371 6381 6415 6434 6446 6448 6461 6479 6506 6540 6541 6683 6688 6794 6795 6830 6862 6881 6901 6931 6941 6991 7051 7104 7123 7158 7160 7176 7192 7201 7270 7271 7311 7312 11091 11141 11172 11221 11314 11361 11385 11390 11406 11409 11430 11442 11481 11549 11587 11664 11677 11761 11916 12839 12869 12872 12896 12906 13000 13019 13078 13103 13205 13206 13229 13276 13290 13326 13436 13487 13502 13503 13504 13623 13626 13739 15664 15703 15707 15799 15823 15876 15886 15890
19 32 96 107 165 168 181 209 266 299 307 351 412 440 444 476 490 507 516 545 548 554 563 581 592 621 666 704 707 732 763 767 835 867 884 959 964 983 992 1056 1090 1126 1130 1150 1153 1160 1172 1178 1226 1241 1306 1349 1462 1467 1476 1526 1549 1554 1556 1585 1601 1624 1643 1651 1685 1732 1827 1871 1874 1891 1892 1938 1944 1970 2002 2024 2052 2053 2085 2094 2132 2145 2173 2238 2253 2299 2309 2355 2463 2473 2508 2527 8420 8455 8461 8471 8473 8508 8542 8544 8571 8675 8680 8681 8700 8719 8748 8764 8822 8840 8867 8888 8926 8936 8986 9043 9074 9185 9194 9234 9245 9362 9375 9409 9446 9455 9469 9480 9513 9542 9550 9592 9719 9734 9755 9811 9832 9850 9892 9911 9969 10000 10042 10067 10100 10131 10135 10181 10191 10198 10222 10224 10227 10267 10301 10326 10328 10454 10496 10628 10631 10633 10653 10659 10667 10700 10709 10710 10717 10719 10735 11941 11979 12024 12048 12066 12067 12080 12085 12087 12130 12163 12167 12178 12203 12258 12270 12313 12316 12325 12384 12413 12418 12423 15607 15611 15630 15641 15649 15655
*/
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n, m;

ll r[N], b[N];

vector<ll> dp[N], num[N];

ll mi[N], ma[N];

ll pref[N], pref2[N];

ll get(ll i, ll j){
	if(i < 0 || i > n) return oo;
	//if(j < mi[i] || j > ma[i]) return oo;
	vector<ll>::iterator it = lower_bound(num[i].begin(), num[i].end(), j);
	if(it == num[i].end()) return oo;
	//cout << (it - num[i].begin()) << "\n";
	return dp[i][it - num[i].begin()];
}

ll cal(ll i, ll l, ll rr){
	ll pos = lower_bound(b + 1, b + m + 1, r[i]) - b;
	if(pos <= l) return ((pref[rr] - pref[l - 1]) - (rr - l + 1) * r[i]);
	else if(pos > rr) return ((rr - l + 1) * r[i] - (pref[rr] - pref[l - 1]));
	else{
		ll sum = 0;
		sum += (l - pos) * r[i] - (pref[pos - 1] - pref[l - 1]);
		sum += (pref[rr] - pref[pos - 1]) - r[i] * (rr - pos + 1);
		return sum;
	}
	/*
	ll sum = 0;
	for(ll j = l; j <= rr; j++) sum += abs(r[i] - b[j]);
	return sum;*/
}

ll min_total_length(vector<int> R, vector<int> B) {
	n = R.size(), m = B.size();
	for(ll i = 1; i <= n; i++) r[i] = R[i - 1];
	for(ll i = 1; i <= m; i++) b[i] = B[i - 1];
	ll lst = 0;
	r[n + 1] = oo;
	for(ll i = 1; i <= m; i++) pref[i] = pref[i - 1] + b[i];
	for(int i = 1; i <= n; i++) pref2[i] = pref2[i - 1] + r[i];
	int cnt = 0;
	for(ll i = 1; i <= n; i++){
		ll temp1 = lower_bound(b + 1, b + m + 1, r[i - 1]) - b;
		ll temp2 = lower_bound(b + 1, b + m + 1, r[i + 1]) - b;
		temp2--;
		if(temp1 > temp2) cnt++;
		if(cnt){
			int val = temp1 - 1;
			if(val <= m && val >= 1){
		//		cout << i << " " << temp1 - 1 << "\n";
				num[i].pb(temp1 - 1);
				if(temp1 <= m && temp1 >= 1)num[i].pb(temp1);
			}
		}
		else cnt = 0;
		ii mn_dist = {oo, oo};
		ll temp = lower_bound(b + 1, b + m + 1, r[i]) - b;
		if(temp <= m){
			temp1 = min(temp1, temp);
			temp2 = max(temp2, temp);
		}
		if(temp > 1){
			temp--;
	//		mn_dist = min(mn_dist, {r[i] - b[temp], temp});
			temp1 = min(temp1, temp);
			temp2 = max(temp2, temp);
		}
	//	assert(mn_dist.fi != oo);
	//	temp1 = min(temp1, mn_dist.se);
	//	temp2 = max(temp2, mn_dist.se);
		//dp[i].resize(temp2 - temp1 + 1);
		//mi[i] = temp1, ma[i] = temp2;
		for(int j = max(1LL, temp1); j <= min(m, temp2); j++) num[i].pb(j);
		//mi[i] = 1, ma[i] = m;
		//dp[i].resize(ma[i] - mi[i] + 1);
		//for(ll j = 0; j < dp[i].size(); j++) dp[i][j] = oo;
	}
	cnt = 0;
	for(ll i = n; i >= 1; i--){
		ll temp1 = lower_bound(b + 1, b + m + 1, r[i - 1]) - b;
		ll temp2 = lower_bound(b + 1, b + m + 1, r[i + 1]) - b;
		temp2--;
		if(temp1 > temp2) cnt++;
		else cnt = 0;
		if(cnt){
			int val = temp1 - 1;
		//	cout << i << " " << val << "\n";
			if(val >= 1 && val <= m) num[i].pb(val);
			val++;
			if(val >= 1 && val <= m) num[i].pb(val);
		}
	}
	//for(int i = 1; i <= n; i++) ma[i] = max(ma[i], ma[i - 1] + 1);
	//for(int i = n - 1; i >= 1; i--) mi[i] = min(mi[i], mi[i + 1] - 1);
	/*
	for(int i = 1; i <= n; i++){
		mi[i] = max(mi[i], 1LL);
		ma[i] = min(ma[i], m);
	}*/
	for(int i = 1; i <= n; i++){
		//if(i >= 14) for(int j = 1; j <= m; j++) num[i].pb(j);
		sort(num[i].begin(), num[i].end());
		num[i].resize(unique(num[i].begin(), num[i].end()) - num[i].begin());
		dp[i].resize(num[i].size());
		for(ll j = 0; j < dp[i].size(); j++) dp[i][j] = oo;
	}
	b[m + 1] = oo;
//	return;
	////return 0;
	num[0].pb(0);
	dp[0].resize(1);
	dp[0][0] = 0;
	int streak = 0;
	for(ll i = 1; i <= n; i++){
		ll itr = 0;
		ll mini = oo;
		int cntt = 0;
		int lst = -1;
		ll temp1 = lower_bound(b + 1, b + m + 1, r[i - 1]) - b;
		ll temp2 = lower_bound(b + 1, b + m + 1, r[i + 1]) - b;
		temp2--;
		if(r[i] < b[temp1]) streak++;
		else streak = 0;
	//	if(temp1 > temp2) cout << "OK1\n";
		ll mini2 = oo;
	//	cout << i << " " << temp1 - 1 << " " << (temp1 > temp2) << "\n";
		for(auto j : num[i]){
			dp[i][cntt] = min(dp[i][cntt], get(i - 1, j) + abs(r[i] - b[j]));
			if(r[i] <= b[temp1] && j >= temp1 && ((i - (j - temp1 + 1)) >= 0)){
				//cout << i << " " << j << " " << cntt << "\n";
				dp[i][cntt] = min(dp[i][cntt], min(get(i - (j - temp1 + 1), temp1 - 1), get(i - (j - temp1 + 1), temp1)) + (pref[j] - pref[temp1 - 1]) - (pref2[i] - pref2[i - (j - temp1 + 1)]));
			//	cout << get(i - (j - temp1 + 1), temp1 - 1) << " " << (pref[j] - pref[temp1 - 1]) - (pref2[i] - pref2[i - (j - temp1 + 1)]) << "\n";
			//	cout << i - (j - temp1) << " " << temp1 << " " << get(i - (j - temp1), temp1) << " " << (pref[j] - pref[temp1] - (pref2[i] - pref2[i - (j - temp1)])) << "\n";
			}
			if(j == (temp1 - 1)){
			//	cout << "OK2\n";
			//cout << streak << "\n";
				dp[i][cntt] = min(dp[i][cntt], min(get(i - streak, j - streak), get(i - streak, j - streak + 1)) + (pref2[i] - pref2[i - streak]) - (pref[j] - pref[j - streak]));
			//	cout << i << " " << j << " " << temp2 << " " << streak << " " << r[i] << " " << b[temp2] << " " << get(i - streak, j - streak) << " " << ((pref2[i] - pref2[i - streak]) - (pref[j] - pref[j - streak])) << "\n";
			}
			/*
			for(ll k = mi[i - 1]; k < j; k++){
				dp[i][j - mi[i]] = min(dp[i][j - mi[i]], get(i - 1, k) + cal(i, k + 1, j));
			}*/
	//		cout << i << " " << j << " " << dp[i][j - mi[i]] << "\n";
			if(lst >= 0){
				mini += cal(i, lst + 1, j);
				mini2 += cal(i, lst + 1, j);
			}
			lst = j;
			while(itr < num[i - 1].size() && num[i - 1][itr] < j){
			//	cout << "OKAY\n";
			//	cout << i - 1 << " " << num[i - 1][itr] << " " << get(i - 1, num[i - 1][itr]) << " " << cal(i, num[i - 1][itr] + 1, j) << "\n";
				mini = min(mini, get(i - 1, num[i - 1][itr]) + cal(i, num[i - 1][itr] + 1, j));
			//	cout << get(i - 1, itr) << " " << cal(i, itr + 1, j) << "\n";
				//cout << get(i - 1, itr - 1) << "\n";
				itr++;
			}
		//	cout << dp[i][cntt] << "\n";
			dp[i][cntt] = min(dp[i][cntt], min(mini, mini2));
			mini2 = min(mini2, dp[i][cntt]);
			//cout << mini << "\n";
		//	cout << i << " " << j << " " << cntt << " " << dp[i][cntt] << "\n";
			cntt++;
		//	cout << i << " " << j << " " << dp[i][j - mi[i]] << "\n";
		}
	}
	return get(n, m);
}

/*
4 5
1 2 3 7
0 4 5 9 10
*/

#ifdef local
void process(){
	ll n, m;
	cin >> n >> m;
	vector<int> r, b;
	for(ll i = 0; i < n; i++){
		ll x;
		cin >> x;
		r.pb(x);
	}
	for(ll i = 0; i < m; i++){
		ll x;
		cin >> x;
		b.pb(x);
	}
	cout << min_total_length(r, b) << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("wiring.inp", "r", stdin);
	freopen("wiring.out", "w", stdout);
	process();
}
#endif

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:93:6: warning: variable 'mn_dist' set but not used [-Wunused-but-set-variable]
   93 |   ii mn_dist = {oo, oo};
      |      ^~~~~~~
wiring.cpp:142:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(ll j = 0; j < dp[i].size(); j++) dp[i][j] = oo;
      |                 ~~^~~~~~~~~~~~~~
wiring.cpp:188:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |    while(itr < num[i - 1].size() && num[i - 1][itr] < j){
      |          ~~~~^~~~~~~~~~~~~~~~~~~
wiring.cpp:74:5: warning: unused variable 'lst' [-Wunused-variable]
   74 |  ll lst = 0;
      |     ^~~

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