fork download
copy 
  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
comments (?)
stdin
copy 
1 6
()(())
stdout
copy 
2
https://ideone.com/dRl8T2
language:
C++14 (gcc 8.3)
created:
2 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!