fork download 
  1. #include<stdio.h>
  2. int tree[1212121], tn;
  3. void insert_g(int w, int g) {
  4. 	for (int i = tn + w; i > 0; i /= 2) {
  5. 		tree[i] += g;
  6. 	}
  7. }
  8. int search_g(int ss,int ee) {
  9. 	int s = ss + tn;
  10. 	int e = ee + tn;
  11. 	int res = 0;
  12. 	while (s <= e) {
  13. 		if (s % 2 == 1)res += tree[s++];
  14. 		if (e % 2 == 0)res += tree[e--];
  15. 		s /= 2; e /= 2;
  16. 	}
  17. 	return res;
  18. }
  19. int W[51515];
  20. int main() {
  21. 	int n, ans = 0 , i;
  22. 	scanf("%d", &n);
  23. 	for (tn = 1; tn <= n * 2; tn *= 2);
  24. 	for (i = 1; i <= 2 * n; i++) {
  25. 		int x;
  26. 		scanf("%d", &x);
  27. 		if (W[x] == 0) {
  28. 			W[x] = i;
  29. 			insert_g(i, 1);
  30. 		}
  31. 		else {
  32. 			ans += search_g(W[x] + 1, i - 1);
  33. 			insert_g(W[x], -1);
  34. 		}
  35. 	}
  36. 	printf("%d", ans);
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 4144KB
comments (?)
stdin 
4
3
2
4
4
1
3
2
1
stdout 
3
https://ideone.com/iz2e5G
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!