fork download 
  1. #include<stdio.h>
  2. #include<set>
  3. #include<map>
  4. using namespace std;
  5. set<int>S;
  6. map<int, int>M;
  7. int a[121212];
  8. int tn, tree[1212121];
  9. void insert_g(int w, int g) {
  10. 	for (int i = w + tn; i > 0; i /= 2)tree[i] += g;
  11. }
  12. int search_g(int ss, int ee) {
  13. 	int s = ss + tn;
  14. 	int e = ee + tn;
  15. 	int res = 0;
  16. 	while (s <= e) {
  17. 		if (s % 2 == 1)res += tree[s++];
  18. 		if (e % 2 == 0)res += tree[e--];
  19. 		s /= 2; e /= 2;
  20. 	}
  21. 	return res;
  22. }
  23. int L[121212], R[121212];
  24.  
  25. int jd(int x) {if (x < 0)return -x; return x;}
  26. int main() {
  27. 	set<int>S;
  28. 	int n;
  29. 	int i, j;
  30. 	scanf("%d", &n);
  31. 	for (tn = 1; tn < n; tn *= 2);
  32. 	for (i = 0; i < n; i++)scanf("%d", &a[i]), S.insert(a[i]);
  33. 	int cnt = 0;
  34. 	for (auto p : S) M[p] = cnt++;
  35. 	for (i = 0; i < n; i++)a[i] = M[a[i]];
  36. 	for (i = 0; i < tn * 2; i++)tree[i] = 0;
  37. 	for (i = 0; i < n; i++)L[i] = search_g(a[i],n-1), insert_g(a[i], 1);
  38. 	for (i = 0; i < tn * 2; i++)tree[i] = 0;
  39. 	for (i = n-1; i >= 0; i--)R[i] = search_g(a[i],n-1), insert_g(a[i], 1);
  40. 	int ans = 0;
  41. 	for (i = 0; i < n; i++) {
  42. 		int x, y;
  43. 		if (L[i] > R[i])x = L[i], y = R[i];
  44. 		else x = R[i], y = L[i];
  45. 		if (x>y*2) ans++;
  46. 	}
  47. 	printf("%d", ans);
  48. 	return 0;
  49. }
Success #stdin #stdout 0.01s 4312KB
comments (?)
stdin 
Standard input is empty
stdout 
14642
https://ideone.com/Xnvdu4
language:
C++ (gcc 8.3)
created:
6 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!