Advertisement
YEZAELP

THACO: robotlineup

Nov 3rd, 2020
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. vector <int> srt;
  7. int n, m;
  8.  
  9. lli merge(int left, int mid, int right){
  10. int temp[n+m];
  11. int i = left, j = mid, k = left;
  12. lli cnt = 0;
  13. while ((i <= mid - 1) && (j <= right)){
  14. if (srt[i] > srt[j]) {
  15. temp[k] = srt[i];
  16. k ++;
  17. i ++;
  18. }
  19. else {
  20. temp[k] = srt[j];
  21. k ++;
  22. j ++;
  23. cnt = cnt + (lli)(mid - i);
  24. }
  25. }
  26. while (i <= mid - 1){
  27. temp[k] = srt[i];
  28. k ++;
  29. i ++;
  30. }
  31. while (j <= right){
  32. temp[k] = srt[j];
  33. k ++;
  34. j ++;
  35. }
  36. for (i = left; i <= right; i++)
  37. srt[i] = temp[i]; //
  38. return cnt;
  39. }
  40.  
  41. lli Sort(int left, int right){
  42. if(right <= left) return 0;
  43. int mid = (right + left) / 2;
  44. lli cnt = Sort(left, mid);
  45. cnt += Sort(mid + 1, right);
  46. cnt += merge(left, mid + 1, right);
  47. return cnt;
  48. }
  49.  
  50. int main() {
  51.  
  52. scanf("%d%d", &n, &m);
  53.  
  54. if (n == 1) {
  55. int x;
  56. lli cnt = 0;
  57. scanf("%d", &x);
  58.  
  59. for(int i=2;i<=m+1;i++){
  60. scanf("%d", &x);
  61. cnt += (lli) i - 1;
  62. }
  63.  
  64. printf("%lld", cnt);
  65. }
  66. else {
  67. int H[n + 1];
  68. for (int i = 1; i <= n; i++) {
  69. scanf("%d", &H[i]);
  70. }
  71.  
  72. double median;
  73. if(n % 2 == 1) median = H[n/2 + 1];
  74. else median = (H[n/2] + H[n/2 + 1]) / 2;
  75.  
  76. int R[m+1];
  77. int l = 1, r = 1;
  78. for (int i = 1; i <= m; i++){
  79. int S;
  80. scanf("%d", &S);
  81. if(S <= median) {
  82. srt.push_back(S);
  83. l ++;
  84. }
  85. else {
  86. R[r] = S;
  87. r ++;
  88. }
  89. }
  90.  
  91. sort(srt.begin(), srt.end());
  92. sort(R+1, R+r);
  93.  
  94. for(int i=1;i<=n;i++) srt.push_back(H[i]);
  95.  
  96. for(int i=1;i<r;i++){
  97. srt.push_back(R[i]);
  98. }
  99.  
  100. printf("%lld", Sort(0, n + m - 1));
  101. }
  102.  
  103. return 0;
  104. }
  105.  
Advertisement
RAW Paste Data Copied
Advertisement