fork(1) download
  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
stdin
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
17999999716