fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll> pi;
  5.  ll maks = 0,mins=1000000010;
  6.  
  7. #define fi first
  8. #define sc second
  9. #define mp make_pair
  10. #define pb push_back
  11.  
  12. vector<pi> pasangan;
  13. vector<ll> dict;
  14.  
  15. ll n;
  16. ll independent = 0;
  17. string a,b;
  18. ll k;
  19. ll x,y;
  20. ll si;
  21.  
  22. ll ternary3(ll x){
  23. 	ll ret = 0;
  24. 	for(ll i=0;i<si;i++) ret+=labs(pasangan[i].fi-x)+labs(pasangan[i].sc-x);
  25. 	return ret;
  26. }
  27.  
  28. ll ternary2(ll x, ll y){
  29. 	ll ret =0;
  30. 	for(ll i=0;i<si;i++){
  31. 		ret+=min(labs(pasangan[i].fi-x)+labs(pasangan[i].sc-x),labs(pasangan[i].fi-y)+labs(pasangan[i].sc-y));
  32. 	}
  33. 	return ret;
  34. }
  35.  
  36. ll ternary1(ll x){
  37. 	ll l = 0,r=dict.size()-1;
  38. 	while(l<r){
  39. 		if (l+10>=r){
  40. 			ll i = l, j = r;
  41. 			ll now =LONG_LONG_MAX;
  42. 			ll ret;
  43. 			for(ll k=i;k<=j;k++){
  44. 				ll sek = ternary2(x,dict[k]);
  45. 				if (sek<now){
  46. 					now=sek;
  47. 					ret=k;
  48. 				}
  49. 			}
  50. 			l=r=ret;
  51. 		}
  52.  
  53. 		ll lt = l+(r-l)/3;
  54. 		ll rt = l+(r-l)*2/3;
  55.  
  56. 		if (ternary2(x,dict[lt])>ternary2(x,dict[rt])) l=lt;
  57. 		else r = rt;
  58. 	}
  59. 	ll kel = ternary2(x,dict[l]), ker = ternary2(x,dict[r]);
  60. 	return min(kel,ker);
  61. }
  62.  
  63. int main(){
  64. 	ios_base::sync_with_stdio(false);
  65. 	cin>>k>>n;
  66. 	while(n--){
  67. 		cin >> a >> x >> b >> y;
  68. 		dict.pb(x); dict.pb(y);
  69. 		maks=max(maks,max(x,y));
  70. 		mins=min(mins,min(x,y));
  71. 		if (a==b) independent += labs(x-y);
  72. 		else{
  73. 			pasangan.pb(mp(x,y));
  74. 		}
  75. 	}
  76.  
  77. 	sort(dict.begin(),dict.end());
  78. 	si = pasangan.size();
  79. 	ll l = 0, r = dict.size()-1;
  80.  
  81. 	if (k==1){
  82. 		while(l<r){
  83. 			if (l+10>=r){
  84. 				ll i = l, j=r;
  85. 				ll now = LONG_LONG_MAX;
  86. 				ll ap;
  87. 				for (ll k=i;k<=j;k++){
  88. 					ll sek = ternary3(dict[k]);
  89. 					if (sek<now){
  90. 						now=sek;
  91. 						ap=k;
  92. 					}
  93. 				}
  94. 				l=r=ap;
  95. 			}
  96. 			ll lt = l+(r-l)/3;
  97. 			ll rt = l+ (r-l)*2/3;
  98.  
  99. 			if (ternary3(dict[lt])>ternary3(dict[rt])) l=lt;
  100. 			else r=rt;
  101. 		}
  102.  
  103. 		independent+=si;
  104. 		cout << independent+min(ternary3(dict[l]),ternary3(dict[r])) << "\n";
  105. 		return 0;
  106. 	}
  107.  
  108. 	while(l<r){
  109. 		if (l+10>=r){
  110. 			ll i = l, j=r;
  111. 			ll now = LONG_LONG_MAX;
  112. 			ll ap;
  113. 			for (ll k=i;k<=j;k++){
  114. 				ll sek = ternary1(dict[k]);
  115. 				if (sek<now){
  116. 					now=sek;
  117. 					ap=k;
  118. 				}
  119. 			}
  120. 			l=r=ap;
  121. 		}
  122. 		ll lt = l+(r-l)/3;
  123. 		ll rt = l+ (r-l)*2/3;
  124.  
  125. 		if (ternary1(dict[lt])>ternary1(dict[rt])) l=lt;
  126. 		else r=rt;
  127. 	}
  128.  
  129. 	independent+=si;
  130. 	cout << independent+min(ternary1(dict[l]),ternary1(dict[r])) << "\n";
  131. }
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
2 20
A 0 B 1000000000
A 1 B 999999999
A 2 B 999999998
A 3 B 999999997
A 4 B 999999996
A 5 B 999999995
A 6 B 999999994
A 7 B 999999993
A 8 B 999999992
A 9 B 999999991
A 10 B 999999990
A 11 B 999999989
A 12 B 999999988
A 13 B 999999987
A 14 B 999999986
A 15 B 999999985
A 16 B 999999984
A 17 B 999999983
A 500000000 B 500000000
A 500000001 B 500000001
stdout
copy 
17999999716
https://ideone.com/UO6QOK
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!