fork download
  1. /*
  2. */
  3. // #pragma GCC optimize("Ofast")
  4. // #pragma GCC target("avx,avx2,fma")
  5.  
  6. #include <iostream>
  7. #include <iomanip>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <string>
  11. #include <cstring>
  12. #include <vector>
  13. #include <map>
  14. #include <unordered_map>
  15. #include <set>
  16. #include <unordered_set>
  17. #include <queue>
  18. #include <stack>
  19. #include <deque>
  20. #include <algorithm>
  21. #include <numeric>
  22. #include <cmath>
  23. #include <utility>
  24. #include <bitset>
  25. #include <random>
  26. #include <chrono>
  27.  
  28. #include <ext/pb_ds/assoc_container.hpp>
  29. #include <ext/pb_ds/tree_policy.hpp>
  30. using namespace __gnu_pbds;
  31. using namespace std;
  32.  
  33. #define EPS 1e-9
  34. #define CeilDiv(a, b) ((a + b - 1) / b)
  35.  
  36. typedef long long ll;
  37. typedef long double ld;
  38. typedef unsigned long long ull;
  39. typedef pair<int, int> pi;
  40. typedef pair<int, double> pid;
  41. typedef pair<ll, ll> pll;
  42. typedef pair<double, double> pd;
  43. typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  44.  
  45. // Comment out #include<iostream>
  46. //ifstream cin("cbs.in");
  47. //ofstream cout("cbs.out");
  48.  
  49. vector<vector<int>> Get_Psum(const vector<string>& brackets)
  50. {
  51. int k = brackets.size(), n = brackets[0].size();
  52. vector<vector<int>> psum(k, vector<int>(n));
  53. for(int i = 0; i < k; ++i)
  54. {
  55. for(int j = 0; j < n; ++j)
  56. {
  57. int val = (brackets[i][j] == '(') ? 1 : -1;
  58. psum[i][j] = val;
  59. if(j > 0) psum[i][j] += psum[i][j-1];
  60. }
  61. }
  62. return psum;
  63. }
  64.  
  65. vector<vector<int>> Get_NearestLeft(const vector<vector<int>>& psum)
  66. {
  67. int k = psum.size(), n = psum[0].size();
  68. vector<vector<int>> res(k, vector<int>(n, -1));
  69. for(int i = 0; i < k; ++i)
  70. {
  71. stack<int> st;
  72. for(int j = n-1; j >= 0; --j)
  73. {
  74. while(!st.empty() && psum[i][j] < psum[i][st.top()])
  75. {
  76. res[i][st.top()] = j;
  77. st.pop();
  78. }
  79. st.push(j);
  80. }
  81. }
  82. return res;
  83. }
  84.  
  85. void Solve(const int &tc = 1)
  86. {
  87. int k, n;
  88. cin >> k >> n;
  89. vector<string> brackets(k);
  90. for(auto& v : brackets)
  91. {
  92. cin >> v;
  93. }
  94.  
  95. vector<vector<int>> psum = Get_Psum(brackets);
  96. vector<vector<int>> nearest_left = Get_NearestLeft(psum);
  97.  
  98. vector<int> super_psum(n);
  99. for(int i = 0; i < k; ++i)
  100. {
  101. for(int j = 0; j < n; ++j)
  102. {
  103. super_psum[j] += psum[i][j];
  104. }
  105. }
  106.  
  107. ll ans = 0;
  108. map<int, vector<int>> idx_of;
  109. // How many concurrently balanced substring ends at index j
  110. for(int j = 0; j < n; ++j)
  111. {
  112. // All brackets[i][j] needs to be )
  113. bool all_close = true;
  114. for(int i = 0; i < k; ++i)
  115. {
  116. all_close &= (brackets[i][j] == ')');
  117. }
  118. if(all_close)
  119. {
  120. // Get max left boundary
  121. int mx_left = -1;
  122. for (int i = 0; i < k; ++i)
  123. {
  124. mx_left = max(mx_left, nearest_left[i][j]);
  125. }
  126.  
  127. // How many target_sum with max_left < idx < j
  128. int target_sum = super_psum[j];
  129. ans += ((int)idx_of[target_sum].size() -
  130. (upper_bound(idx_of[target_sum].begin(), idx_of[target_sum].end(), mx_left) - idx_of[target_sum].begin()));
  131. }
  132.  
  133. idx_of[super_psum[j]].push_back(j);
  134. }
  135.  
  136. cout << ans << "\n";
  137. }
  138.  
  139. int main()
  140. {
  141. std::ios::sync_with_stdio(false);
  142. cin.tie(0);
  143. //cout << fixed << setprecision(9);
  144.  
  145. int tc = 1;
  146. //cin >> tc;
  147. for (int i = 1; i <= tc; ++i)
  148. {
  149. Solve(i);
  150. }
  151. return 0;
  152. }
Success #stdin #stdout 0s 5552KB
stdin
1 6
()(())
stdout
2