Advertisement
aakib_alam

LongestValidParenthesis

Aug 11th, 2022
618
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.46 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #pragma GCC target("avx,avx2,fma")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. #define ff first
  10. #define ss second
  11. #define ll long long
  12. #define pb push_back
  13. #define vi vector<int>
  14. #define vll vector<ll>
  15. #define vvi vector<vi>
  16. #define vb vector<bool>
  17. #define vpii vector<pii>
  18. #define pii pair<int, int>
  19. #define Size(v) (int)v.size()
  20. #define all(v) v.begin(), v.end()
  21. #define ffor(i, a, n) for (int i = a; i < n; i++)
  22. #define rfor(i, a, n) for (int i = n - 1; i >= a; i--)
  23. int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
  24. int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
  25. string yon[] = {"NO", "YES"};
  26. template <class T>
  27. using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  28. template <class T>
  29. using muloset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. /*      -------------------------DEBUGGING----------------------------       */
  31. #ifndef ONLINE_JUDGE
  32. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  33. #else
  34. #define debug(x...)
  35. #endif
  36. void __print(ll x) {cerr << x;}
  37. void __print(int x) {cerr << x;}
  38. void __print(char x) {cerr << x;}
  39. void __print(bool x) {cerr << x;}
  40. void __print(double x) {cerr << x;}
  41. void __print(string x) {cerr << x;}
  42. template<typename T, typename V>
  43. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  44. template<typename T>
  45. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  46. void _print() {cerr << "]\n";}
  47. template <typename T, typename... V>
  48. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  49.  
  50. const int MAXN = 100005;
  51. const int mod = 1000000007;
  52. const double eps = 0.00000001;
  53.  
  54. inline int add(int x, int y) { int ret = x + y; if (ret >= mod) ret -= mod; return ret; }
  55. inline int sub(int x, int y) { int ret = (x - y); if (ret < 0) ret += mod; return ret; }
  56. inline int mul(int x, int y) { int ret = (1ll * x * y) % mod; return ret; }
  57. int exp(int a, int b) { int ret = 1; while (b) { if (b & 1) ret = mul(ret, a); a = mul(a, a); b >>= 1;} return ret; }
  58. int dv(int a, int b) { int ret = exp(b, mod - 2); ret = mul(ret, a); return ret; }
  59.  
  60. int fun(string s) {
  61.     int n = (int)s.size();
  62.     stack<int> st;
  63.     vi lst(n + 1, -1);
  64.     ffor(i, 0, n) {
  65.         if (s[i] == '(') {
  66.             st.push(i);
  67.             continue;
  68.         }
  69.         if (!st.empty()) {
  70.             lst[i + 1] = st.top();
  71.             st.pop();
  72.         }
  73.     }
  74.     int ans = 0;
  75.     vi dp(n + 1);
  76.     ffor(i, 0, n) {
  77.         if (lst[i + 1] != -1) {
  78.             dp[i + 1] = dp[lst[i + 1]] + (i + 1 - lst[i + 1]);
  79.             ans = max(ans, dp[i + 1]);
  80.         }
  81.     }
  82.     return ans;
  83. }
  84.  
  85. int main()
  86. {
  87.     ios_base ::sync_with_stdio(false);
  88.     cin.tie(NULL);
  89.     cout.tie(NULL);
  90.  
  91. #ifndef ONLINE_JUDGE
  92.     freopen("input.txt", "r", stdin);
  93.     freopen("output.txt", "w", stdout);
  94.     freopen("error.txt", "w", stderr);
  95. #endif
  96.  
  97.     auto start = std::chrono::high_resolution_clock::now();
  98.  
  99.     int tc = 1;
  100.     // cin >> tc;
  101.     for (int t = 1; t <= tc; t++)
  102.     {
  103.         // cout << "Case #" << t << ": ";
  104.         string s;
  105.         cin >> s;
  106.         cout << fun(s) << "\n";
  107.     }
  108.  
  109.     auto stop = std::chrono::high_resolution_clock::now();
  110.     auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);
  111.     cerr << "Time taken : " << ((double)duration.count()) / ((double) 1e9) << "s " << endl;
  112.  
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement