fork download
copy 
  1. // https://w...content-available-to-author-only...f.com/CDLS23TS/problems/CDLS23H
  2.  
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5.  
  6. #ifdef DEBUG
  7. #include "debug.h"
  8. #else
  9. #define see(...) ;
  10. #endif
  11.  
  12. #define int int64_t
  13. #define sz(x) (int)(x.size())
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define F0R(i, R) for (int i = (0); i < (R); ++i)
  16. #define FOR(i, L, R) for (int i = (L); i <= (R); ++i)
  17.  
  18. #include <complex>
  19. const double PI = acos(-1);
  20.  
  21. namespace fft {
  22. typedef complex<double> base;
  23. void fft(vector<base>& v, bool inv) {
  24. 	vector<base> w(v.size());
  25. 	for (int i = 2; i <= sz(v); i <<= 1) {
  26. 		int bsz = v.size() / i;
  27. 		base ang(cos(2 * PI / i), sin(2 * PI / i));
  28. 		if (inv)
  29. 			ang = base(1, 0) / ang;
  30. 		for (int j = 0; j < bsz; j++) {
  31. 			for (int k = 0; k < i; k++) {
  32. 				w[k] = v[bsz * k + j];
  33. 			}
  34. 			base pw(1, 0);
  35. 			for (int k = 0; k < i / 2; k++) {
  36. 				base a = w[2 * k], b = w[2 * k + 1] * pw;
  37. 				v[bsz * k + j] = a + b;
  38. 				v[bsz * k + j + v.size() / 2] = a - b;
  39. 				pw *= ang;
  40. 			}
  41. 		}
  42. 	}
  43. 	if (inv) {
  44. 		for (int i = 0; i < sz(v); i++) {
  45. 			v[i] /= v.size();
  46. 		}
  47. 	}
  48. }
  49. vector<int> multiply(vector<int>& v, vector<int>& w) {
  50. 	vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
  51. 	int n = 1;
  52. 	while (n < max(sz(v), sz(w)))
  53. 		n <<= 1;
  54. 	n <<= 1;
  55. 	fv.resize(n);
  56. 	fw.resize(n);
  57. 	fft(fv, 0);
  58. 	fft(fw, 0);
  59. 	for (int i = 0; i < n; i++)
  60. 		fv[i] *= fw[i];
  61. 	fft(fv, 1);
  62. 	vector<int> ret(n);
  63. 	for (int i = 0; i < n; i++)
  64. 		ret[i] = round(fv[i].real());
  65. 	return ret;
  66. }
  67. } // namespace fft
  68.  
  69. int32_t main() {
  70. 	ios::sync_with_stdio(0);
  71. 	cin.tie(0);
  72. 	int n;
  73. 	cin >> n;
  74. 	vector<int> pos(2 * n + 1, 0), neg(2 * n + 1, 0);
  75. 	F0R(i, n) {
  76. 		int val;
  77. 		cin >> val;
  78. 		if (val > 0) {
  79. 			pos[i] = 1;
  80. 		} else if (val < 0) {
  81. 			neg[-i + n] = 1;
  82. 		}
  83. 	}
  84. 	vector<int> product = fft::multiply(pos, neg);
  85. 	const int MX = sz(product);
  86. 	vector<int> distance_counter(MX + 1, 0);
  87. 	F0R(dist, MX) {
  88. 		if (product[dist] > 0) {
  89. 			int d = abs(dist - n);
  90. 			distance_counter[d] += product[dist];
  91. 		}
  92. 	}
  93. 	vector<int> answer_counter(MX + 1, 0);
  94.  
  95. 	FOR(k, 1, MX) {
  96. 		for (int multiple = k; multiple <= MX; multiple += k) {
  97. 			answer_counter[k] += distance_counter[multiple];
  98. 		}
  99. 	}
  100.  
  101. 	int Q;
  102. 	cin >> Q;
  103. 	while (Q--) {
  104. 		int K;
  105. 		cin >> K;
  106. 		int answer = K <= MX ? answer_counter[K] : 0;
  107. 		cout << answer << " ";
  108. 	}
  109.  
  110. 	return 0;
  111. }
Runtime error #stdin #stdout #stderr 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/HIEzzC
language:
C++14 (gcc 8.3)
created:
1 year 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!