fork download
copy 
  1. #include <algorithm>
  2. #include <cstring>
  3. #include <cstdio>
  4. using namespace std;
  5. const int MAX = 1000005;
  6. int ans[MAX], rmq[20][MAX], r[21][MAX], pos[MAX], size[MAX], lg[MAX];
  7. pair<int, pair<pair<int, int>, pair<int, int> > > qq[MAX];
  8. pair<pair<int, int>, int> p[MAX];
  9. int lcp(int x, int y)
  10. {
  11. 	int lim = min(size[x], size[y]);
  12. 	int ans = 0;
  13. 	for (int i = lg[lim]; i >= 0; i--)
  14. 		if (r[i][x] == r[i][y])
  15. 		{
  16. 			x += (1 << i);
  17. 			y += (1 << i);
  18. 			ans |= (1 << i);
  19. 		}
  20. 	return ans;
  21. }
  22. int fen[MAX], a[MAX];
  23. void add(int p, int val)
  24. {
  25. 	for (p++; p < MAX; p += p & -p)
  26. 		fen[p] += val;
  27. }
  28. int get(int p)
  29. {
  30. 	int ans = 0;
  31. 	for (; p > 0; p -= p & -p)
  32. 		ans += fen[p];
  33. 	return ans;
  34. }
  35. char s[MAX], t[MAX];
  36. int main()
  37. {
  38. 	for (int i = 2; i < MAX; i++)
  39. 		lg[i] = lg[i / 2] + 1;
  40. 	int n, q;
  41. 	scanf("%d %d", &n, &q);
  42. 	int last = 0;
  43. 	for (int i = 0; i < n; i++)
  44. 	{
  45. 		scanf("%s", t);
  46. 		int m = strlen(t);
  47. 		pos[i] = last;
  48. 		for (int j = 0; j < m; j++)
  49. 		{
  50. 			size[last] = m;
  51. 			s[last++] = t[j];
  52. 		}
  53. 		size[last] = m;
  54. 		s[last++] = '#';
  55. 	}
  56. 	pos[n] = last;
  57. 	n = last;
  58. 	for (int i = 0; i < n; i++)
  59. 		if (s[i] == '#')
  60. 			r[0][i] = i + 1000;
  61. 		else
  62. 			r[0][i] = s[i];
  63. 	for (int i = 1; i <= 20; i++)
  64. 	{
  65. 		for (int j = 0; j < n; j++)
  66. 			if (j + (1 << (i - 1)) >= n)
  67. 				p[j] = make_pair(make_pair(r[i - 1][j], -1), j);
  68. 			else
  69. 				p[j] = make_pair(make_pair(r[i - 1][j], r[i - 1][j + (1 << (i - 1))]), j);
  70. 		sort(p, p + n);
  71. 		for (int j = 0; j < n; j++)
  72. 			if (j > 0 && p[j].first == p[j - 1].first)
  73. 				r[i][p[j].second] = r[i][p[j - 1].second];
  74. 			else
  75. 				r[i][p[j].second] = j + 1;
  76. 	}
  77. 	for (int i = 0; i < n; i++)
  78. 	{
  79. 		a[i] = r[20][i] - 1;
  80. 		p[i] = make_pair(make_pair(a[i], -1), i);
  81. 	}
  82. 	sort(p, p + n);
  83. 	for (int i = 0; i < n - 1; i++)
  84. 		rmq[0][i] = lcp(p[i].second, p[i + 1].second);
  85. 	for (int i = 1; i < 20; i++)
  86. 		for (int j = 0; j < n - 1; j++)
  87. 			if (j + (1 << (i - 1)) >= n - 1)
  88. 				rmq[i][j] = rmq[i - 1][j];
  89. 			else
  90. 				rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
  91. 	int t = 0;
  92. 	for (int ind = 0; ind < q; ind++)
  93. 	{
  94. 		int l, r, k;
  95. 		scanf("%d %d %d", &l, &r, &k);
  96. 		l--;
  97. 		k--;
  98. 		l = pos[l];
  99. 		r = pos[r];
  100. 		int s = pos[k];
  101. 		int e = pos[k + 1] - 1;
  102. 		int lo = a[s], hi = a[s] + 1;
  103. 		for (int i = 19; i >= 0; i--)
  104. 		{
  105. 			if (lo - (1 << i) >= 0 && rmq[i][lo - (1 << i)] >= e - s)
  106. 				lo -= (1 << i);
  107. 			if (hi + (1 << i) <= n && rmq[i][hi - 1] >= e - s)
  108. 				hi += (1 << i);
  109. 		}
  110. 		qq[t++] = make_pair(lo, make_pair(make_pair(l, r), make_pair(-1, ind)));
  111. 		qq[t++] = make_pair(hi, make_pair(make_pair(l, r), make_pair(1, ind)));
  112. 	}
  113. 	sort(qq, qq + t);
  114. 	int pos = 0;
  115. 	for (int i = 0; i < t; i++)
  116. 	{
  117. 		while (pos < n && p[pos].first.first < qq[i].first)
  118. 			add(p[pos++].second, 1);
  119. 		ans[qq[i].second.second.second] += qq[i].second.second.first * (get(qq[i].second.first.second) - get(qq[i].second.first.first));
  120. 	}
  121. 	for (int i = 0; i < q; i++)
  122. 		printf("%d\n", ans[i]);
  123. 	return 0;
  124. }
  125.  
Time limit exceeded #stdin #stdout 5s 219968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uS0U0f
language:
C++14 (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!