oj.uz

답안 #761282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761282 2023-06-19T12:58:28 Z minhcool 전선 연결 (IOI17_wiring) C++17
100 / 100
 127 ms 35296 KB 
//#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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14496 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14432 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14408 KB Output is correct
13 Correct 8 ms 14416 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14464 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14368 KB Output is correct
2 Correct 8 ms 14464 KB Output is correct
3 Correct 49 ms 26376 KB Output is correct
4 Correct 50 ms 26356 KB Output is correct
5 Correct 40 ms 24088 KB Output is correct
6 Correct 57 ms 28872 KB Output is correct
7 Correct 57 ms 28876 KB Output is correct
8 Correct 57 ms 28896 KB Output is correct
9 Correct 57 ms 28868 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Correct 8 ms 14348 KB Output is correct
3 Correct 119 ms 33708 KB Output is correct
4 Correct 124 ms 35060 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 11 ms 14420 KB Output is correct
10 Correct 8 ms 14440 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 7 ms 14416 KB Output is correct
15 Correct 8 ms 14408 KB Output is correct
16 Correct 9 ms 14412 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 120 ms 33608 KB Output is correct
19 Correct 121 ms 33620 KB Output is correct
20 Correct 122 ms 35296 KB Output is correct
21 Correct 126 ms 33640 KB Output is correct
22 Correct 127 ms 33876 KB Output is correct
23 Correct 121 ms 33928 KB Output is correct
24 Correct 123 ms 34076 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 105 ms 34456 KB Output is correct
3 Correct 111 ms 34496 KB Output is correct
4 Correct 104 ms 34828 KB Output is correct
5 Correct 116 ms 34596 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14352 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 8 ms 14408 KB Output is correct
14 Correct 9 ms 14404 KB Output is correct
15 Correct 7 ms 14396 KB Output is correct
16 Correct 8 ms 14408 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 93 ms 32200 KB Output is correct
19 Correct 106 ms 34516 KB Output is correct
20 Correct 118 ms 34668 KB Output is correct
21 Correct 104 ms 33736 KB Output is correct
22 Correct 92 ms 31676 KB Output is correct
23 Correct 107 ms 31948 KB Output is correct
24 Correct 93 ms 32532 KB Output is correct

Subtask #5
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14496 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14432 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14408 KB Output is correct
13 Correct 8 ms 14416 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14464 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14368 KB Output is correct
18 Correct 8 ms 14464 KB Output is correct
19 Correct 49 ms 26376 KB Output is correct
20 Correct 50 ms 26356 KB Output is correct
21 Correct 40 ms 24088 KB Output is correct
22 Correct 57 ms 28872 KB Output is correct
23 Correct 57 ms 28876 KB Output is correct
24 Correct 57 ms 28896 KB Output is correct
25 Correct 57 ms 28868 KB Output is correct
26 Correct 7 ms 14416 KB Output is correct
27 Correct 8 ms 14348 KB Output is correct
28 Correct 119 ms 33708 KB Output is correct
29 Correct 124 ms 35060 KB Output is correct
30 Correct 9 ms 14420 KB Output is correct
31 Correct 8 ms 14412 KB Output is correct
32 Correct 7 ms 14412 KB Output is correct
33 Correct 7 ms 14416 KB Output is correct
34 Correct 11 ms 14420 KB Output is correct
35 Correct 8 ms 14440 KB Output is correct
36 Correct 7 ms 14420 KB Output is correct
37 Correct 8 ms 14420 KB Output is correct
38 Correct 7 ms 14420 KB Output is correct
39 Correct 7 ms 14416 KB Output is correct
40 Correct 8 ms 14408 KB Output is correct
41 Correct 9 ms 14412 KB Output is correct
42 Correct 8 ms 14420 KB Output is correct
43 Correct 120 ms 33608 KB Output is correct
44 Correct 121 ms 33620 KB Output is correct
45 Correct 122 ms 35296 KB Output is correct
46 Correct 126 ms 33640 KB Output is correct
47 Correct 127 ms 33876 KB Output is correct
48 Correct 121 ms 33928 KB Output is correct
49 Correct 123 ms 34076 KB Output is correct
50 Correct 8 ms 14420 KB Output is correct
51 Correct 105 ms 34456 KB Output is correct
52 Correct 111 ms 34496 KB Output is correct
53 Correct 104 ms 34828 KB Output is correct
54 Correct 116 ms 34596 KB Output is correct
55 Correct 7 ms 14420 KB Output is correct
56 Correct 8 ms 14420 KB Output is correct
57 Correct 8 ms 14420 KB Output is correct
58 Correct 7 ms 14420 KB Output is correct
59 Correct 7 ms 14352 KB Output is correct
60 Correct 7 ms 14420 KB Output is correct
61 Correct 9 ms 14420 KB Output is correct
62 Correct 8 ms 14408 KB Output is correct
63 Correct 9 ms 14404 KB Output is correct
64 Correct 7 ms 14396 KB Output is correct
65 Correct 8 ms 14408 KB Output is correct
66 Correct 8 ms 14420 KB Output is correct
67 Correct 93 ms 32200 KB Output is correct
68 Correct 106 ms 34516 KB Output is correct
69 Correct 118 ms 34668 KB Output is correct
70 Correct 104 ms 33736 KB Output is correct
71 Correct 92 ms 31676 KB Output is correct
72 Correct 107 ms 31948 KB Output is correct
73 Correct 93 ms 32532 KB Output is correct
74 Correct 90 ms 31040 KB Output is correct
75 Correct 100 ms 32768 KB Output is correct
76 Correct 95 ms 32080 KB Output is correct
77 Correct 105 ms 33644 KB Output is correct
78 Correct 105 ms 33724 KB Output is correct
79 Correct 108 ms 34256 KB Output is correct
80 Correct 89 ms 31280 KB Output is correct
81 Correct 87 ms 30508 KB Output is correct
82 Correct 92 ms 32880 KB Output is correct
83 Correct 70 ms 29984 KB Output is correct
84 Correct 71 ms 29836 KB Output is correct
85 Correct 105 ms 34560 KB Output is correct
86 Correct 90 ms 31684 KB Output is correct
87 Correct 95 ms 32688 KB Output is correct
88 Correct 92 ms 32340 KB Output is correct
89 Correct 111 ms 32456 KB Output is correct
90 Correct 95 ms 33236 KB Output is correct
91 Correct 104 ms 33860 KB Output is correct
92 Correct 99 ms 33480 KB Output is correct
93 Correct 90 ms 31908 KB Output is correct
94 Correct 104 ms 34740 KB Output is correct
95 Correct 105 ms 34120 KB Output is correct
96 Correct 83 ms 30908 KB Output is correct
97 Correct 96 ms 33604 KB Output is correct
98 Correct 101 ms 33660 KB Output is correct
99 Correct 97 ms 33736 KB Output is correct
100 Correct 119 ms 34972 KB Output is correct
101 Correct 100 ms 31260 KB Output is correct
102 Correct 94 ms 31852 KB Output is correct