fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define db long double
  10. #define onBit(mask , i) (mask | (1 << i))
  11. #define offBit(mask , i) (mask & (~(1 << i)))
  12. #define int long long
  13.  
  14. const long long INF = 1e16;
  15. const int N = 5e5 + 7;
  16. const long long MAXN = 1e9 + 7;
  17. long long c_l[N] , c_r[N] , c[N] , _a[N] , _b[N];
  18. int n;
  19.  
  20. struct gv{
  21. 	long long val;
  22. 	int id;
  23. };
  24.  
  25. gv a[N] , b[N];
  26.  
  27. bool cmp(gv x , gv y){
  28. 	if (x.val != y.val) return x.val < y.val;
  29. 	return x.id < y.id;
  30. }
  31.  
  32. void inp(){
  33. 	cin >> n;
  34. 	for (int i = 1 ; i <= n ; ++i){
  35. 		cin >> a[i].val;
  36. 		_a[i] = a[i].val;
  37. 		a[i].id = i;
  38. 	}
  39. 	for (int i = 1 ; i <= n ; ++i){
  40. 		cin >> b[i].val;
  41. 		_b[i] = b[i].val;
  42. 		b[i].id = i;
  43. 	}
  44. 	sort(a + 1 , a + n + 1 , cmp);
  45. 	sort(b + 1 , b + n + 1 , cmp);
  46. }
  47.  
  48. void ktao(){
  49. 	for (int i = 2 ; i <= n ; ++i){
  50. 		c_l[i] = (i - 1) * (i - 2) / 2;
  51. 	}
  52. 	for (int i = n - 1 ; i >= 1 ; --i){
  53. 		c_r[i] = (n - i) * (n - i - 1) / 2;
  54. 	}
  55. }
  56.  
  57. long long nl_a(int i_l , int i_r , int j_l , int j_r){
  58. 	long long res = 0;
  59. 	c[j_l - 1] = 0;
  60. 	c[j_l] = b[j_l].id;
  61. 	for (int i = j_l + 1 ; i <= j_r ; ++i){
  62. 		c[i] = c[i - 1] + b[i].id;
  63. 	}
  64. 	int id = j_l;
  65. 	for (int i = i_l ; i <= i_r ; ++i){
  66. 		if (a[i].id <= b[id].id) continue;
  67. 		while (id < j_r && a[i].id > b[id + 1].id) ++id;
  68. 		int l = j_l , r = id , mid , pos = j_l - 1;
  69. 		while (l <= r){
  70. 			mid = (l + r) >> 1;
  71. 			if (n - a[i].id + 1 >= b[mid].id){
  72. 				pos = mid;
  73. 				l = mid + 1;
  74. 			}
  75. 			else r = mid - 1;
  76. 		}
  77. 		res += c[pos] + (id - pos) * (n - a[i].id + 1);
  78. 	}
  79. 	return res;
  80. }
  81.  
  82. long long nl_b(int i_l , int i_r , int j_l , int j_r){
  83. 	long long res = 0;
  84. 	c[j_l - 1] = 0;
  85. 	c[j_l] = a[j_l].id;
  86. 	for (int i = j_l + 1 ; i <= j_r ; ++i){
  87. 		c[i] = c[i - 1] + a[i].id;
  88. 	}
  89. 	int id = j_l;
  90. 	for (int i = i_l ; i <= i_r ; ++i){
  91. 		if (b[i].id <= a[id].id) continue;
  92. 		while (id < j_r && b[i].id > a[id + 1].id) ++id;
  93. 		int l = j_l , r = id , mid , pos = j_l - 1;
  94. 		while (l <= r){
  95. 			mid = (l + r) >> 1;
  96. 			if (n - b[i].id + 1 >= a[mid].id){
  97. 				pos = mid;
  98. 				l = mid + 1;
  99. 			}
  100. 			else r = mid - 1;
  101. 		}
  102. 		res += c[pos] + (id - pos) * (n - b[i].id + 1);
  103. 	}
  104. 	return res;
  105. }
  106.  
  107. void solve(){
  108. 	ktao();
  109. 	long long res = 0;
  110. 	int i = 1 , j = 1;
  111. 	while (i <= n && j <= n){
  112. 		if (a[i].val < b[j].val){
  113. 			int u = i;
  114. 			while (u < n && a[u + 1].val == a[i].val) ++u;
  115. 			i = u + 1;
  116. 			continue;
  117. 		}
  118. 		if (a[i].val > b[j].val){
  119. 			int v = j;
  120. 			while (v < n && b[v + 1].val == b[j].val) ++v;
  121. 			j = v + 1;
  122. 			continue;
  123. 		}
  124. 		int u = i , v = j;
  125. 		while (u < n && a[u + 1].val == a[i].val) ++u;
  126. 		while (v < n && b[v + 1].val == b[j].val) ++v;
  127. 		res += nl_a(i , u , j , v) + nl_b(j , v , i , u);
  128. 		i = u + 1 , j = v + 1;
  129. 	}
  130. 	for (int i = 1 ; i <= n ; ++i){
  131. 		if (_a[i] == _b[i]){
  132. 			res += c_l[i] + c_r[i] + min(n - i , i - 1) + n;
  133. 		}
  134. 	}
  135. 	cout << res;
  136. }
  137.  
  138. signed main(){
  139. //	freopen("xhmax.inp" , "r" , stdin);
  140. //	freopen("xhmax.out" , "w" , stdout);
  141.     faster;
  142.     inp();
  143.     solve();
  144. //    return 0;
  145. }
  146.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/AnxJ8K
language:
C++14 (gcc 8.3)
created:
10 days 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!