fork download
copy 
  1. /*                ___
  2.    _______________| |_
  3.   /\                  \
  4.  /  \                  \
  5. /____\__________________\
  6. |    |                  |
  7. |    | Date : 26/07/2025|
  8. |    | Author : pppssslc|
  9. |____|__________________|
  10. */
  11. #include<bits/stdc++.h>
  12.  
  13. using namespace std;
  14.  
  15. typedef string str;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef double db;
  19. typedef long double ldb;
  20. typedef pair<int, int> pii;
  21. typedef pair<ll, ll> pll;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vl;
  24. typedef vector<vector<int>> vii;
  25. typedef vector<vector<ll>> vll;
  26. typedef map<int, int> mpii;
  27. typedef map<ll, ll> mpll;
  28. typedef set<int> si;
  29. typedef set<ll> sl;
  30. typedef complex<double> cd;
  31. #define prio_que priority_queue
  32.  
  33. #define se second
  34. #define fi first
  35. #define For(i, l, r, x) for(int i = l; i <= r; i += x)
  36. #define Ford(i, l, r, x) for(int i = l; i >= r; i -= x)
  37. #define Fore(x, a) for(auto x: a)
  38. #define pb push_back
  39. #define ins insert
  40. #define all(a) a.begin(), a.end()
  41.  
  42. #define phongdeptrainhatquadat main()
  43.  
  44. const ll inf = 1e18 + 1;
  45. const int mod = 1e9 + 7;
  46. const int maxn = 1e5 + 1;
  47. const int offset = 5e4 + 1;
  48. const db PI = acos(-1);
  49.  
  50. void fft(vector<cd> &a, bool inv){
  51. 	int n = a.size();
  52. 	if(n <= 1) return;
  53. 	int j = 0;
  54. 	For(i, 1, n, 1){
  55. 		int bit = n >> 1;
  56. 		for(; j&bit; bit >>= 1) j ^= bit;
  57. 		j ^= bit;
  58. 		if(i < j) swap(a[i], a[j]);
  59. 	}
  60. 	For(len, 2, n, len){
  61. 		db ang = 2 * PI / len * (inv ? -1 : 1);
  62. 		cd wlen(cos(ang), sin(ang));
  63. 		For(i, 0, n - 1, len){
  64. 			cd w(1);
  65. 			For(j, 0, len / 2 - 1, 1){
  66. 				cd u = a[i + j];
  67. 				cd v = a[i + j + len / 2] * w;
  68. 				a[i + j] = u + v;
  69. 				a[i + j + len / 2] = u - v;
  70. 				w *= wlen;
  71. 			}
  72. 		}
  73. 	}
  74. 	if(inv) for(cd &x: a) x /= n;
  75. }
  76.  
  77. int phongdeptrainhatquadat{
  78. 	ios_base::sync_with_stdio(false);
  79. 	cin.tie(NULL); cout.tie(NULL);
  80. 	int n; cin >> n;
  81. 	int maxA = 0, maxB = 0;
  82. 	vi cntA(maxn, 0), cntB(maxn, 0);
  83. 	For(i, 1, n, 1){
  84. 		int v; cin >> v;
  85. 		++cntA[v + offset], maxA = max(maxA, v);
  86. 	}
  87. 	For(i, 1, n, 1){
  88. 		int v; cin >> v;
  89. 		++cntB[v + offset], maxB = max(maxB, v);
  90. 	}
  91. 	int N = 1;
  92. 	while(N <= 2 * maxn) N <<= 1;
  93. 	vector<cd> polyA(N), polyB(N);
  94. 	For(i, 0, maxn, 1) polyA[i] = cntA[i];
  95. 	For(i, 0, maxn, 1) polyB[i] = cntB[i];
  96. 	fft(polyA, false); fft(polyB, false);
  97. 	vector<cd> polyR(N);
  98. 	For(i, 0, N, 1) polyR[i] = polyA[i] * polyB[i];
  99. 	fft(polyR, true);
  100. 	vl cnt(N);
  101. 	For(i, 0, N - 1, 1) cnt[i] = round(polyR[i].real());
  102. 	ll res = 0;
  103. 	For(i, 1, n, 1){
  104. 		int v; cin >> v; int s = v + 2 * offset;
  105. 		if(s < N) res += cnt[s];
  106. 	}
  107. 	cout << res;
  108. 	return (0 ^ 0);
  109. }
Success #stdin #stdout 0.11s 18424KB
comments (?)
stdin
copy 
3
-1 1 1
-1 2 3
2 3 -2
stdout
copy 
4
https://ideone.com/wSPpSw
language:
C++ (gcc 8.3)
created:
6 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!