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 = 1e6 + 10, mod = 1e9+7;
  18.  
  19. static long long bit[2][2*mx];
  20. int a[mx];
  21. int n, base = 1e6+1;
  22. vector<int> positions[mx], compress;
  23. map<int, int> mp;
  24. //map<int, vector<int> > positions;
  25.  
  26. inline void up(long long bit[], int i, long long v)
  27. {
  28. 	for (; i<2*mx; i+=i&-i)
  29. 		bit[i] += v;
  30. }
  31.  
  32. inline long long qu(long long bit[], int i)
  33. {
  34. 	long long ret = 0;
  35. 	for (; i; i-=i&-i)
  36. 		ret += bit[i];
  37. 	return ret;
  38. }
  39.  
  40. inline void update(int s, int e, int c)
  41. {
  42. 	up(bit[0], s, c); up(bit[0], e+1, -c);
  43. 	up(bit[1], s, c*(1-s)); up(bit[1], e+1, c*e);
  44. }
  45.  
  46. inline long long query(int i)
  47. {
  48. 	return qu(bit[0], i)*i + qu(bit[1], i);
  49. }
  50.  
  51. long long process(int num)
  52. {
  53. 	long long ret = 0;
  54. 	vector< pair<int, int> > moves;
  55.  
  56. 	positions[num].push_back(n+1);
  57. 	int end = base, start = end - (positions[num][0]-1);
  58.  
  59. 	update(start, end, 1);
  60. 	moves.push_back(make_pair(start, end));
  61.  
  62. 	rep(i, 0, positions[num].size()-2)
  63. 	{
  64. 		int end = 2*(i+1) - positions[num][i] + base-1;
  65. 		int start = end - (positions[num][i+1]-positions[num][i]-1);
  66.  
  67. 		long long get = 0;
  68. 		int idx = end;
  69. 		do
  70. 		{
  71. 			get = query(idx);
  72. 			ret += get;
  73. 			idx--;
  74. 		} while(get > 0 and idx >= start);
  75.  
  76. 		update(start+1, end+1, 1);
  77. 		moves.push_back(make_pair(start+1, end+1));
  78. 	}
  79.  
  80. 	rep(i, 0, moves.size()-1)
  81. 		update(moves[i].first, moves[i].second, -1);
  82.  
  83. 	return ret;
  84. }
  85.  
  86. int main()
  87. {
  88. 	//rf;// wf;
  89. 	ios::sync_with_stdio(0);
  90.  
  91. 	cin >> n;
  92. 	assert(0 < n and n<=1e6);
  93. 	rep(i, 1, n)
  94. 	{
  95. 		cin >> a[i];
  96. 		assert(0 < a[i] and a[i] <= 1e9);
  97. 		compress.push_back(a[i]);
  98. 		//positions[a[i]].push_back(i);
  99. 	}
  100. 	sort(compress.begin(), compress.end());
  101. 	compress.erase(unique(compress.begin(), compress.end()), compress.end());
  102.  
  103. 	rep(i, 0, compress.size()-1)
  104. 		mp[compress[i]] = i;
  105. 	rep(i, 1, n)
  106. 		positions[mp[a[i]]].push_back(i);
  107.  
  108. 	long long ans = 0;
  109. 	//map<int, vector<int> >::iterator it = positions.begin();
  110. 	//for(; it!=positions.end(); ++it)
  111. 	//	ans += process(it->first);
  112. 	for(int i = 0; i<mx; ++i)
  113. 		if(positions[i].size())
  114. 			ans += process(i);
  115.  
  116. 	cout << ans << '\n';
  117.  
  118. 	return 0;
  119. }
  120.  
Runtime error #stdin #stdout #stderr 0s 50296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:92: int main(): Assertion `0 < n and n<=1e6' failed.
https://ideone.com/zyPAFG
language:
C++ (gcc 8.3)
created:
8 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!