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 p = 7; 
  12. const int MOD[2] = {(int)1e9 + 2277, (int)1e9 + 9277};  
  13. const int N = 2e6 + 5;  
  14.  
  15. int n;   
  16. string s; 
  17. int pref[2 * N];  
  18.  
  19. int getIndex(char c) {
  20. 	if (c == '(') return 1; 
  21. 	return 2; 
  22. }
  23.  
  24. int p_pow[2][2 * N], h[2][2 * N]; 
  25.  
  26. void precompute() {
  27. 	for (int i = 0; i <= 1; i++) {
  28. 		p_pow[i][0] = 1; 
  29. 		for (int j = 1; j <= 2 * n; j++) p_pow[i][j] = 1ll * p_pow[i][j - 1] * p % MOD[i]; 
  30. 	}
  31.  
  32. 	for (int i = 0; i <= 1; i++) {
  33. 		h[i][0] = 0; 
  34. 		for (int j = 1; j <= 2 * n; j++) h[i][j] = (1ll * h[i][j - 1] * p + getIndex(s[j])) % MOD[i];
  35. 	}
  36. }
  37.  
  38. ii getHash(int l, int r) {
  39. 	ii ans; 
  40. 	ans.first = (h[0][r] - 1ll * h[0][l - 1] * p_pow[0][r - l + 1] % MOD[0] + MOD[0]) % MOD[0]; 
  41. 	ans.second = (h[1][r] - 1ll * h[1][l - 1] * p_pow[1][r - l + 1] % MOD[1] + MOD[1]) % MOD[1]; 
  42. 	return ans; 
  43. }
  44.  
  45. int seg[4 * 2 * N];
  46.  
  47. void build(int id, int l, int r) {
  48. 	if (l == r) {
  49. 		seg[id] = pref[l]; 
  50. 		return; 
  51. 	}
  52. 	int mid = (l + r) >> 1; 
  53. 	build(id * 2, l, mid); 
  54. 	build(id * 2 + 1, mid + 1, r); 
  55. 	seg[id] = min(seg[id * 2], seg[id * 2 + 1]); 
  56. } 
  57.  
  58. int getMin(int id, int l, int r, int u, int v) {
  59. 	if (l > v || r < u) return INF;   
  60.  
  61. 	if (u <= l && r <= v) return seg[id];  
  62.  
  63. 	int mid = (l + r) >> 1;  
  64. 	return min(getMin(id * 2, l, mid, u, v), getMin(id * 2 + 1, mid + 1, r, u, v)); 
  65. }
  66.  
  67. int getSum(int l, int r) {
  68. 	return pref[r] - pref[l - 1];
  69. }
  70.  
  71. int main() {
  72. 	ios::sync_with_stdio(false); 
  73. 	cin.tie(nullptr);  	
  74. 	cin >> n; 
  75. 	cin >> s; 
  76. 	s = ' ' + s + s; 
  77.  
  78. 	for (int i = 1; i <= 2 * n; i++) {
  79. 		int c = (s[i] == '(') ? 1 : -1;  
  80. 		pref[i] = pref[i - 1] + c;  
  81. 	}
  82.  
  83. 	precompute();  
  84. 	build(1, 1, 2 * n);   
  85.  
  86. 	vector<ii> hs;  
  87. 	for (int i = 1; i <= n; i++) {
  88. 		int l = i, r = i + n - 1;  
  89. 		bool is_balanced = ((getMin(1, 1, 2 * n, l, r) - pref[l - 1] >= 0) && (getSum(l, r) == 0)); 
  90. 		if (is_balanced) hs.push_back(getHash(l, r)); 
  91. 	}
  92.  
  93. 	sort(hs.begin(), hs.end());   
  94. 	hs.resize(unique(hs.begin(), hs.end()) - hs.begin()); 
  95.  
  96. 	cout << hs.size() << '\n'; 
  97. }
Success #stdin #stdout 0.01s 11760KB
comments (?)
stdin
copy 
4
(())
stdout
copy 
1
https://ideone.com/MwR1sz
language:
C++14 (gcc 8.3)
created:
333 days 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!