fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N = 500005;
  5. ll inter[N];
  6. int n, arr[N], _arr[N];
  7. int ls(int indx) {
  8. 	return indx & (-indx);
  9. }
  10. void update(int indx, int val) {
  11. 	for (; indx <= n; indx += ls(indx))
  12. 		inter[indx] += val;
  13. }
  14. ll get(int indx) {
  15. 	ll res = 0;
  16. 	for (; indx > 0; indx -= ls(indx))
  17. 		res += inter[indx];
  18. 	return res;
  19. }
  20. int main() {
  21. 	cin >> n;
  22. 	for (int i = 0; i < n; ++i)
  23. 		cin >> arr[i], _arr[i] = arr[i];
  24. 	int pos = -1;
  25. 	ll ans = 0, mx = 0;
  26. 	for (int i = n - 1; i >= 0; --i) {
  27. 		ll tmp = get(arr[i]);
  28. 		ans += tmp;
  29. 		update(arr[i], 1);
  30. 		if (tmp >= mx) {
  31. 			mx = tmp;
  32. 			pos = i;
  33. 		}
  34. 	}
  35. 	if (pos == -1) {
  36. 		cout << "Cool Array" << endl;
  37. 		return 0;
  38. 	}
  39. 	int x = pos;
  40. 	reverse(arr, arr + n);
  41. 	for (int i = 0; i < n; ++i)
  42. 		arr[i] = n - arr[i] + 1;
  43. 	ll _ans = 0, _mx = 0;
  44. 	pos = -1;
  45. 	ll cnt = 0;
  46. 	memset(inter, 0, sizeof(inter));
  47. 	for (int i = n - 1 - x; i >= 0; --i) {
  48.  
  49. 		ll tmp = get(arr[i])-cnt;
  50. 		update(arr[i], 1);
  51. 		if (tmp > _mx) {
  52. 			_mx = tmp;
  53. 			pos = i;
  54. 		}
  55. 		cnt+=arr[i] < arr[n-x-1];
  56. 	}
  57. 	if (pos == -1)
  58. 		cout << "Cool Array" << endl;
  59. 	else
  60. 		cout << x + 1 << " " << n - pos << endl;
  61. 	return 0;
  62. }
  63.  
Success #stdin #stdout 0s 11272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Cool Array
https://ideone.com/Jz0v2t
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!