fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <string>
  10. #include <cstring>
  11. #include <queue>
  12. #include <cassert>
  13. #define rf freopen("in.in", "r", stdin)
  14. #define wf freopen("out.out", "w", stdout)
  15. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  16. using namespace std;
  17. const int mx = 5e5 + 10, mod = 1e9+7;
  18.  
  19. static long long bit[2][2*mx];
  20. int a[mx];
  21. int n, base = 5e5+1;
  22. pair<int, int> num_pos[mx], moves[mx];
  23.  
  24. inline void up(long long bit[], int i, long long v)
  25. {
  26. 	for (; i<2*mx; i+=i&-i)
  27. 		bit[i] += v;
  28. }
  29.  
  30. inline long long qu(long long bit[], int i)
  31. {
  32. 	long long ret = 0;
  33. 	for (; i; i-=i&-i)
  34. 		ret += bit[i];
  35. 	return ret;
  36. }
  37.  
  38. inline void update(int s, int e, int c)
  39. {
  40. 	up(bit[0], s, c); up(bit[0], e+1, -c);
  41. 	up(bit[1], s, c*(1-s)); up(bit[1], e+1, c*e);
  42. }
  43.  
  44. inline long long query(int i)
  45. {
  46. 	return qu(bit[0], i)*i + qu(bit[1], i);
  47. }
  48.  
  49. long long process(int &idx)
  50. {
  51. 	long long ret = 0;
  52. 	int moves_idx = 0;
  53.  
  54. 	int end = base, start = end - (num_pos[idx].second-1), range_start = idx;
  55.  
  56. 	update(start, end, 1);
  57. 	moves[++moves_idx] = make_pair(start, end);
  58.  
  59. 	while(num_pos[idx].first == num_pos[range_start].first)
  60. 	{
  61. 		int end = 2*(idx-range_start+1) - num_pos[idx].second + base-1;
  62. 		int nextid = (num_pos[idx].first != num_pos[idx+1].first)? n+1: num_pos[idx+1].second;
  63. 		int start = end - (nextid - num_pos[idx].second-1);
  64. 		idx++;
  65.  
  66. 		long long get = 0;
  67. 		int iter = end;
  68. 		do
  69. 		{
  70. 			get = query(iter);
  71. 			ret += get;
  72. 			iter--;
  73. 		} while(get > 0 and iter >= start);
  74.  
  75. 		update(start+1, end+1, 1);
  76. 		moves[++moves_idx] = make_pair(start+1, end+1);
  77. 	}
  78.  
  79. 	rep(i, 1, moves_idx)
  80. 		update(moves[i].first, moves[i].second, -1);
  81.  
  82. 	return ret;
  83. }
  84.  
  85. int main()
  86. {
  87. 	//rf;// wf;
  88. 	ios::sync_with_stdio(0);
  89.  
  90. 	cin >> n;
  91. 	assert(0 < n and n<=5e5);
  92. 	rep(i, 1, n)
  93. 	{
  94. 		cin >> a[i];
  95. 		assert(0 < a[i] and a[i] <= 1e9);
  96.  
  97. 		num_pos[i] = make_pair(a[i], i);
  98. 	}
  99.  
  100. 	sort(num_pos+1, num_pos+n+1);
  101.  
  102. 	long long ans = 0;
  103. 	int idx = 1;
  104. 	while(idx <= n)
  105. 		ans += process(idx);
  106.  
  107. 	cout << ans << '\n';
  108.  
  109. 	return 0;
  110. }
  111.  
Success #stdin #stdout 0s 28800KB
comments ()
stdin
copy 
7
1 2 3 3 2 1 3
stdout
copy 
11
https://ideone.com/xHkWh7
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!