fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define pf push_front
  6. typedef long long ll;
  7. string s;
  8. ll seg_len[10000005];
  9. ll seg_left[1000005];
  10. ll seg_right[10000005];
  11.  
  12. ll min(ll a,ll b){return a<b?a:b;}
  13. typedef struct {ll left;ll right;ll length;} scratch;
  14. void make(int ss,int se,int si)
  15. {
  16.     if(ss==se){seg_len[si]=0;seg_left[si]=(s[ss]=='(')?1:0;seg_right[si]=(s[ss]==')')?1:0;/*if(ss==17){puts("sup");}*/return;}
  17.  // if((qs<=ss)&&(qe>=se)){return;} 
  18.     int mid=(ss+se)/2;
  19.     make(ss,mid,(2*si)+1);
  20.     make(mid+1,se,(2*si)+2);
  21.     seg_left[si] = seg_left[(2*si)+1]+seg_left[(2*si)+2]-min(seg_left[(2*si)+1],seg_right[(2*si)+2]);  
  22.     seg_right[si]= seg_right[(2*si)+1]+seg_right[(2*si)+2]-min(seg_left[(2*si)+1],seg_right[(2*si)+2]);
  23.     seg_len[si]=seg_len[(2*si)+1]+seg_len[(2*si)+2]+2*min(seg_left[(2*si)+1],seg_right[(2*si)+2]);
  24. }
  25. const scratch sup={0,0,0};
  26. scratch create(scratch sc1,scratch sc2)
  27. {
  28.  scratch sc3;
  29.     sc3.left=sc1.left+sc2.left-min(sc1.left,sc2.right);
  30.     sc3.right=sc1.right+sc2.right-min(sc1.left,sc2.right);
  31.     sc3.length= sc1.length+sc2.length+2*min(sc1.left,sc2.right); 
  32. return sc3;
  33. }
  34. scratch sct;
  35. scratch get(int ss,int se,int si,int qs, int qe)
  36. {
  37.      if(qs>se||qe<ss)
  38.     {
  39.         sct.length=0;
  40.     sct.left=0;
  41.     sct.right=0;
  42.      return sct;  
  43.     }
  44.  
  45.    if((qs<=ss)&&(qe>=se))
  46.    {sct.length=seg_len[si];
  47.     sct.left=seg_left[si];
  48.     sct.right=seg_right[si];
  49.      return sct;  
  50.    } 
  51.  
  52.    int mid=(ss+se)/2;
  53.    return create(get(ss,mid,(2*si)+1,qs,qe),get(mid+1,se,(2*si)+2,qs,qe));
  54. }
  55.  
  56. int main()
  57. {
  58.   memset(seg_len,0,sizeof seg_len);
  59.   memset(seg_left,0,sizeof seg_left);
  60.     memset(seg_right,0,sizeof seg_right);
  61.     cin>>s;
  62.     int n=s.length();
  63.     int m ;scanf("%d",&m);
  64.     make(0,n-1,0);
  65.    // for(int i=0;i<30;i++){printf("%lld %lld %lld -->%d\n",seg_left[i],seg_right[i],seg_len[i],i);}
  66.    // puts("___________________________________________");
  67.     while(m--)
  68.     {
  69.         int start,end;
  70.         scanf("%d%d",&start,&end);start=start-1;end=end-1;
  71.         scratch res=get(0,n-1,0,start,end);
  72.         printf("%lld\n",res.length);
  73.     }
  74. /*scratch res=get(0,n-1,0,1,2);
  75.         printf("%lld\n",res.length);*/
  76.     return 0;
  77. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZHQ3LW
language:
C++ (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!