fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define lld long long
  4. #define MAX 100005
  5.  
  6. using namespace std;
  7.  
  8. lld array[ MAX + 1 ];
  9. lld tree[ 4 * MAX + 1 ];
  10.  
  11. void init(int i, int start, int end ) {
  12.  
  13.     if(start==end)
  14.     {
  15.         tree[i] = array[start];
  16.         return;
  17.     }
  18.     int mid = (start+end)/2;
  19.     init(2*i,start,mid);
  20.     init(2*i+1,mid+1,end);
  21.     tree[i] = tree[2*i] + tree[2*i+1];
  22. }
  23.  
  24. lld query( int i, int start, int end, int qs, int qe ) {
  25.  
  26.     if(start>end||qs>end||qe<start)
  27.         return 0;
  28.     if(qs<=start&&qe>=end)
  29.         return tree[i];
  30.  
  31.     int mid = (start+end)/2;
  32.     return query(2*i,start,mid,qs,qe) + query(2*i+1,mid+1,end,qs,qe);
  33. }
  34.  
  35. char str[MAX];
  36. struct strNode
  37. {
  38.     int sum1,sum2,sum3,sum4,minsum1,minsum2,minsum3,minsum4;
  39. }stree[4*MAX+1];
  40.  
  41. void sinit(int Node,int i,int j)
  42. {
  43.     if(i==j)
  44.     {
  45.         int x = 0;
  46.         stree[Node].sum1 = stree[Node].minsum1 = x;
  47.         stree[Node].sum2 = stree[Node].minsum2 = x;
  48.         stree[Node].sum3 = stree[Node].minsum3 = x;
  49.         stree[Node].sum4 = stree[Node].minsum4 = x;
  50.  
  51.         if(str[i]=='(')
  52.             stree[Node].sum1 = stree[Node].minsum1 += 1;
  53.         else if(str[i]==')')
  54.             stree[Node].sum1 = stree[Node].minsum1 -= 1;
  55.         else if(str[i]=='{')
  56.             stree[Node].sum2 = stree[Node].minsum2 += 1;
  57.         else if(str[i]=='}')
  58.             stree[Node].sum2 = stree[Node].minsum2 -= 1;
  59.         else if(str[i]=='<')
  60.             stree[Node].sum3 = stree[Node].minsum3 += 1;
  61.         else if(str[i]=='>')
  62.             stree[Node].sum3 = stree[Node].minsum3 -= 1;
  63.         else if(str[i]=='[')
  64.             stree[Node].sum4 = stree[Node].minsum4 += 1;
  65.         else if(str[i]==']')
  66.             stree[Node].sum4 = stree[Node].minsum4 -= 1;
  67. 		return;
  68.     }
  69.     int m = (i+j)/2;
  70.  
  71. 	sinit(2*Node, i, m);
  72. 	sinit(2*Node+1, m+1, j);
  73.  
  74. 	stree[Node].sum1 = stree[2*Node].sum1 + stree[2*Node+1].sum1;
  75. 	stree[Node].minsum1 = min(stree[2*Node].minsum1, stree[2*Node].sum1 + stree[2*Node+1].minsum1);
  76. 	stree[Node].sum2 = stree[2*Node].sum2 + stree[2*Node+1].sum2;
  77. 	stree[Node].minsum2 = min(stree[2*Node].minsum2, stree[2*Node].sum2 + stree[2*Node+1].minsum2);
  78. 	stree[Node].sum3 = stree[2*Node].sum3 + stree[2*Node+1].sum3;
  79. 	stree[Node].minsum3 = min(stree[2*Node].minsum3, stree[2*Node].sum3 + stree[2*Node+1].minsum3);
  80. 	stree[Node].sum4 = stree[2*Node].sum4 + stree[2*Node+1].sum4;
  81. 	stree[Node].minsum4 = min(stree[2*Node].minsum4, stree[2*Node].sum4 + stree[2*Node+1].minsum4);
  82. }
  83.  
  84. strNode squery(int i,int start,int end,int qs,int qe)
  85. {
  86.     if(start>end||qs>end||qe<start)
  87.     {
  88.         strNode temp;
  89.         temp.sum1 = LONG_MIN;
  90.         return temp;
  91.     }
  92.  
  93.     if(qs<=start&&qe>=end)
  94.         return stree[i];
  95.  
  96.     int mid = (start + end)/2;
  97.  
  98.     strNode id1 = squery(2*i,start,mid,qs,qe);
  99.     strNode id2 = squery(2*i+1,mid+1,end,qs,qe);
  100.  
  101.     if(id1.sum1==LONG_MIN)return id2;
  102.     if(id2.sum1==LONG_MIN)return id1;
  103.  
  104.     strNode temp;
  105.  
  106.     temp.sum1 = id1.sum1 + id2.sum1;
  107. 	temp.minsum1 = min(id1.minsum1, id1.sum1 + id2.minsum1);
  108. 	temp.sum2 = id1.sum2 + id2.sum2;
  109. 	temp.minsum2 = min(id1.minsum2, id1.sum2 + id2.minsum2);
  110. 	temp.sum3 = id1.sum3 + id2.sum3;
  111. 	temp.minsum3 = min(id1.minsum3, id1.sum3 + id2.minsum3);
  112. 	temp.sum4 = id1.sum4 + id2.sum4;
  113. 	temp.minsum4 = min(id1.minsum4, id1.sum4 + id2.minsum4);
  114.  
  115.     return temp;
  116. }
  117.  
  118.  
  119. int main() {
  120.     int i, N, q, l, r,t;
  121.  
  122.  
  123.     cin>>t;
  124.  
  125.     while(t--)
  126.     {
  127.     cin>>N;
  128.  
  129.     cin>>str;
  130.  
  131.     sinit(1, 0, N - 1);
  132.  
  133.     for ( i = 0; i < N; i++ ) {
  134.         cin>>array[i];
  135.     }
  136.     init(1, 0, N - 1 );
  137.     lld count = 0;
  138.  
  139.     stack<int> s1,s2,s3,s4;
  140.  
  141.     s1.push(0);
  142.     s2.push(0);
  143.     s3.push(0);
  144.     s4.push(0);
  145.  
  146.     int b1 = 0,b2 = 0,b3 = 0,b4 = 0;
  147.  
  148.     for(int i=1;str[i]!='\0';i++)
  149.     {
  150.         int last_idx = 0;
  151.  
  152.         if(str[i]=='('||str[i]=='<'||str[i]=='['||str[i]=='{')
  153.         {
  154.         if(str[i]=='(')
  155.             s1.push(i);
  156.         else if(str[i] == '[')
  157.             s2.push(i);
  158.         else if(str[i]=='{')
  159.             s3.push(i);
  160.         else
  161.             s4.push(i);
  162.         continue;
  163.         }
  164.  
  165.         if(str[i]==')')
  166.         {
  167.             last_idx = s1.top();
  168.             s1.pop();
  169.             if(s1.empty())
  170.                 s1.push(0);
  171.         }
  172.         else if(str[i] == ']'){
  173.             last_idx = s2.top();
  174.  
  175.             s2.pop();
  176.             if(s2.empty())
  177.                 s2.push(0);
  178.         }
  179.         else if(str[i]=='}')
  180.         {
  181.           last_idx = s3.top();
  182.           s3.pop();
  183.             if(s3.empty())
  184.                 s3.push(0);
  185.         }
  186.         else
  187.         {
  188.             last_idx = s4.top();
  189.             s4.pop();
  190.             if(s4.empty())
  191.                 s4.push(0);
  192.         }
  193.  
  194.         strNode xx = squery(1,0,N-1,last_idx,i);
  195.         if(xx.sum1==0&&xx.minsum1==0&&xx.sum2==0&&xx.minsum2==0&&xx.sum3==0&&xx.minsum3==0&&xx.sum4==0&&xx.minsum4==0)
  196.             count = max(count,query(1,0,N-1,last_idx,i));
  197.     }
  198.     printf("%lld\n",count);
  199.     }
  200.     return 0;
  201. }
  202.  
Success #stdin #stdout 0s 19752KB
comments (?)
stdin
copy 
3
4
()()
-1 -2 3 4
4
(()]
-1 -2 3 4
4
[{]{
1 2 3 4
stdout
copy 
7
1
0
https://ideone.com/Querdb
language:
C++ (gcc 8.3)
created:
9 years 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!