fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 5e3 + 5; 
  12.  
  13. int n, q;  
  14. string s;  
  15.  
  16. bool dp[N][N]; // dp[l][r] = true/false = Xâu con s[l..r] có phải là xâu đối xứng hay không
  17. ll sum[N][N]; 
  18.  
  19. void precompute() {
  20. 	for (int l = 1; l <= n; l++) {
  21. 		dp[l][l] = 1;  
  22. 		if (l + 1 <= n) dp[l][l + 1] = (s[l] == s[l + 1]); 
  23. 	}
  24.  
  25. 	for (int l = n; l >= 1; l--) {
  26. 		for (int r = l + 2; r <= n; r++) {
  27. 			dp[l][r] = (s[l] == s[r]) & dp[l + 1][r - 1]; 
  28. 		}
  29. 	}
  30.  
  31. 	for (int i = 1; i <= n; i++) {
  32. 		for (int j = 1; j <= n; j++) sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + dp[i][j]; 
  33. 	}
  34. }
  35.  
  36. int getSum(int x1, int y1, int x2, int y2) {
  37. 	return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]; 
  38. }
  39.  
  40. int main() {
  41. 	ios::sync_with_stdio(false); 
  42. 	cin.tie(nullptr); 	
  43. 	cin >> s >> q; 
  44. 	n = s.size();  
  45. 	s = ' ' + s;  
  46.  
  47. 	precompute();  
  48.  
  49. 	while (q--) {
  50. 		int l, r; 
  51. 		cin >> l >> r;
  52. 		ll ans = getSum(l, l, r, r);
  53. 		cout << ans << '\n'; 
  54. 	}
  55. }
Success #stdin #stdout 0.01s 5648KB
comments (?)
stdin
copy 
caaaba
5
1 1
1 4
2 3
4 6
4 5
stdout
copy 
1
7
3
4
2
https://ideone.com/Q0QjEl
language:
C++14 (gcc 8.3)
created:
1 year 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!