fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int N = 1e4;
  7. int n, q, a[N], seg[N << 2];
  8. char z[31], s[N][31];
  9. unordered_map<ll, int> idx;
  10.  
  11. int calc(char *s) {
  12. 	int n = strlen(s), ret = 0;
  13. 	bool ok1, ok2;
  14. 	for (int i = 0; i < n; ++i) {
  15. 		ok1 = ok2 = true;
  16. 		for (int j = 0;; ++j) {
  17. 			if (i + j < n && i - j >= 0 && s[i + j] == s[i - j] && ok1)
  18. 				++ret;
  19. 			else
  20. 				ok1 = false;
  21. 			if (i + j + 1 < n && i - j >= 0 && s[i + j + 1] == s[i - j] && ok2)
  22. 				++ret;
  23. 			else
  24. 				ok2 = false;
  25. 			if (!ok1 && !ok2)
  26. 				break;
  27. 		}
  28. 	}
  29. 	return ret;
  30. }
  31.  
  32. inline ll getHash(char *s) {
  33. 	ll res = 0;
  34. 	for (int i = 0; s[i]; ++i)
  35. 		res = res * 4 + (s[i] - 'a' + 1);
  36. 	return res;
  37. }
  38.  
  39. void build(int index, int l, int r) {
  40. 	if (l == r) {
  41. 		seg[index] = l;
  42. 		return;
  43. 	}
  44. 	int mid = (l + r) >> 1;
  45. 	build(index << 1, l, mid);
  46. 	build((index << 1) + 1, mid + 1, r);
  47. 	seg[index] = a[seg[index << 1]] >= a[seg[(index << 1) + 1]] ? seg[index << 1] : seg[(index << 1) + 1];
  48. }
  49.  
  50. int get(int index, int r, int l, int s, int e) {
  51. 	if (l < s || r > e)
  52. 		return -1;
  53. 	if (s <= r && l <= e)
  54. 		return seg[index];
  55. 	int mid = (r + l) >> 1;
  56. 	int c1 = get(index << 1, r, mid, s, e);
  57. 	int c2 = get((index << 1) + 1, mid + 1, l, s, e);
  58. 	if (c1 == -1)
  59. 		return c2;
  60. 	if (c2 == -1)
  61. 		return c1;
  62. 	return a[c1] >= a[c2] ? c1 : c2;
  63. }
  64.  
  65. int main(int argc, char **argv) {
  66. 	int t;
  67. 	scanf("%d", &t);
  68. 	while (t-- != 0) {
  69. 		scanf("%d%d", &n, &q);
  70. 		for (int i = 0; i < n; ++i)
  71. 			scanf("%s", s[i]);
  72. 		idx.clear();
  73. 		for (int i = 0; i < n; ++i) {
  74. 			a[i] = calc(s[i]);
  75. 			idx[getHash(s[i])] = i;
  76. 		}
  77. 		build(1, 0, n - 1);
  78. 		while (q-- != 0) {
  79. 			scanf("%s", z);
  80. 			ll l = idx[getHash(z)];
  81. 			scanf("%s", z);
  82. 			ll r = idx[getHash(z)];
  83. 			if (r < l)
  84. 				swap(l, r);
  85. 			printf("%d\n", get(1, 0, n - 1, l, r) + 1);
  86. 		}
  87. 	}
  88. 	return 0;
  89. }
Time limit exceeded #stdin #stdout 5s 8069120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UPsA6o
language:
C++ (gcc 8.3)
created:
7 years 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!