fork download
copy 
  1. #include <iostream>
  2. #define N 750
  3. using namespace std;
  4.  
  5. void merge_sort(int *arr, int n) {
  6. 	if (n == 1) return;
  7. 	int len_l = n / 2, len_r = n - len_l;
  8. 	int l[len_l], r[len_r];
  9. 	for (int i = 0; i < n; i++)
  10. 		if (i < len_l) l[i] = arr[i];
  11. 		else r[i - len_l] = arr[i];
  12. 	merge_sort(l, len_l);
  13. 	merge_sort(r, len_r);
  14. 	int i = 0, j = 0;
  15. 	while (i < len_l && j < len_r)
  16. 		if (l[i] < r[j]) arr[i + j] = l[i++];
  17. 		else arr[i + j] = r[j++];
  18. 	while (i < len_l) arr[i + j] = l[i++];
  19. 	while (j < len_r) arr[i + j] = r[j++];
  20. }
  21.  
  22. int main() {
  23. 	int n, m, MIN[N], MAX[N];
  24. 	cin >> n >> m;
  25. 	for (int i = 0; i < n; i++) {
  26. 		for (int j = 0; j < m; j++) {
  27. 			int input;
  28. 			cin >> input;
  29. 			if (i == 0) MAX[j] = input;
  30. 			else if (MAX[j] < input) MAX[j] = input;
  31. 			if (j == 0) MIN[i] = input;
  32. 			else if (MIN[i] > input) MIN[i] = input;
  33. 		}
  34. 	}
  35. 	merge_sort(MAX, m);
  36. 	merge_sort(MIN, n);
  37. 	int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;
  38. 	while (i < n && j < m) {
  39. 		while (i < n-1 && MIN[i] == MIN[i+1]) {
  40. 			count_i++;
  41. 			i++;
  42. 		} 
  43. 		while (j < m-1 && MAX[j] == MAX[j+1]) {
  44. 			count_j++;
  45. 			j++;
  46. 		}
  47. 		if (MIN[i] < MAX[j]) {
  48. 			i++;
  49. 			count_i = 1;
  50. 		} else if (MIN[i] > MAX[j]) {
  51. 			j++;
  52. 			count_j = 1;
  53. 		} else {
  54. 			counter += count_i * count_j;
  55. 			i++;
  56. 			j++;
  57. 			count_i = 1;
  58. 			count_j = 1;
  59. 		}
  60. 	}
  61. 	while (i < n && MIN[i] <= MAX[m-1]) {
  62. 		while (i < n-1 && MIN[i] == MIN[i+1]) {
  63. 			count_i++;
  64. 			i++;
  65. 		} 
  66. 		if (MIN[i] == MAX[m-1]) {
  67. 			i++;
  68. 			counter += count_i;
  69. 			count_i = 1;
  70. 		}
  71.  
  72. 	}
  73. 	while (j < m && MAX[j] <= MIN[n-1]) {
  74. 		while (j < m-1 && MAX[j] == MAX[j+1]) {
  75. 			count_j++;
  76. 			j++;
  77. 		} 
  78. 		if (MAX[j] == MIN[n-1]) {
  79. 			j++;
  80. 			counter += count_j;
  81. 			count_j = 1;
  82. 		}
  83.  
  84. 	}
  85. 	cout << counter;
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 4
4 5 6 7
3 4 5 6
3 5 6 7
stdout
copy 
1
https://ideone.com/CobfZn
Седловые точки ультра
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!