fork(1) download
copy 
  1. /*
  2.  * 5c.cpp
  3.  * 2018-03-22 12:15
  4.  */
  5.  
  6. #include <iostream>
  7. #include <stack>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. class Solution {
  13. private:
  14.  
  15. public:
  16.     void solve(string &s) {
  17.         stack<int> st;
  18.         int p=0,q,len,maxl=0,maxc=1;
  19.         for (int i=0;i<s.size();) {
  20.             if (s[i]=='(') {
  21.                 st.push(i);
  22.                 i++;
  23.             }
  24.             else if (!st.empty()) {
  25.                 len = i-st.top()+1;
  26.                 st.pop();
  27.                 if (len>maxl) {
  28.                     maxl = len;
  29.                 }
  30.                 else if (len==maxl) {
  31.                     maxc++;
  32.                 }
  33.             }
  34.         }
  35.         cout << maxl << ' ' << maxc << endl;
  36.     }
  37.  
  38.     void solve1(string s) {
  39.         int n=s.size(),maxl=0,maxc=1,len;
  40.         vector<int> c(n,-1),d(n,-1);
  41.         stack<int> in;
  42.         for (int i=0;i<n;i++) {
  43.             if (s[i]=='(') {
  44.                 in.push(i);
  45.             }
  46.             else if (!in.empty()) {
  47.                 d[i] = in.top();
  48.                 in.pop();
  49.                 c[i] = (c[d[i]-1]!=-1) ? c[d[i]-1] : d[i] ;
  50.                 len=i-c[i]+1;
  51.                 if (len>maxl) {
  52.                     maxl = len;
  53.                     maxc = 1;
  54.                 }
  55.                 else if (len==maxl) {
  56.                     maxc++;
  57.                     //cout <<"LEN" << len <<' ' <<  i << endl;
  58.                 }
  59.             }
  60.         }
  61.         //for (int i=0;i<n;i++) {
  62.         //    cout << c[i] << ' ' << d[i] << endl;
  63.         //}
  64.         cout << maxl << ' ' << maxc << endl;
  65.     }
  66. };
  67.  
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(false);
  71.     //cin.tie(NULL);
  72.     string s;
  73.     cin >> s;
  74.     Solution().solve1(s);
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
()(())()
stdout
copy 
8 1
https://ideone.com/yxXKJJ
language:
C++14 (gcc 8.3)
created:
6 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!