fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long int
  6. #define hell (ll)(1e9+7)
  7. #define rep(i,a,b) for(int i=a;i<b;i++)
  8. #define sep(i,a,b) for(int i=a-1;i>=b;i--)
  9.  
  10. // opencount ->no of '(' in string
  11. // closecount -> no of ')' in string
  12. // open -> no of '(' required to the left of string for valid expression
  13. // close -> no of ')' required to the right of string for valid expression
  14. struct g
  15. {
  16.     ll open,close,opencount,closecount;
  17. };
  18.  
  19. vector <ll> a;
  20. vector <g> tree;
  21.  
  22. g merger(g l,g r)
  23. {
  24.     g ans;
  25.     ans.closecount=l.closecount+r.closecount;
  26.     ans.opencount=l.opencount+r.opencount;
  27.     ans.open=max((ll)0,ans.closecount-ans.opencount);
  28.     ans.close=max((ll)0,ans.opencount-ans.closecount);
  29.     return ans;
  30. }
  31.  
  32. void build_tree(ll node,ll s,ll e)
  33. {
  34.     if(s==e)
  35.     {
  36.         if(a[s]==1)
  37.         {
  38.             tree[node].opencount=tree[node].close=1;
  39.             tree[node].closecount=tree[node].open=0;
  40.         }
  41.         else
  42.         {
  43.             tree[node].closecount=tree[node].open=1;
  44.             tree[node].opencount=tree[node].close=0;
  45.         }
  46.         return;
  47.     }
  48.     ll m=(s+e)/2;
  49.     build_tree(node*2,s,m);
  50.     build_tree(node*2+1,m+1,e);
  51.     tree[node]=merger(tree[node*2],tree[node*2+1]);
  52. }
  53.  
  54. void update_tree(ll node,ll s,ll e,ll id)
  55. {
  56.     if(s==e)
  57.     {
  58.         if(a[s]==1)
  59.         a[s]=-1;
  60.         else
  61.         a[s]=1;
  62.         if(a[s]==1)
  63.         {
  64.             tree[node].opencount=tree[node].close=1;
  65.             tree[node].closecount=tree[node].open=0;
  66.         }
  67.         else
  68.         {
  69.             tree[node].closecount=tree[node].open=1;
  70.             tree[node].opencount=tree[node].close=0;
  71.         }
  72.         return;
  73.     }
  74.     ll m=(s+e)/2;
  75.     if(s<=id&&id<=m)
  76.     update_tree(node*2,s,m,id);
  77.     else
  78.     update_tree(node*2+1,m+1,e,id);
  79.     tree[node]=merger(tree[node*2],tree[node*2+1]);
  80. }
  81.  
  82. int main()
  83. {
  84.     //ios_base::sync_with_stdio(false);
  85.     //cin.tie(0);
  86.     for(int t=1;t<=10;t++)
  87.     {
  88.         ll n;
  89.         string s;
  90.         cin>>n>>s;
  91.         a.resize(n);
  92.         tree.resize(4*n);
  93.         rep(i,0,n)
  94.         {
  95.             if(s[i]=='(')
  96.             a[i]=1;
  97.             else
  98.             a[i]=-1;
  99.         }
  100.         cout<<"Test "<<t<<":\n";
  101.         build_tree(1,0,n-1);
  102.         ll q;
  103.         cin>>q;
  104.         while(q--)
  105.         {
  106.             ll k;
  107.             cin>>k;
  108.             g ans;
  109.             if(k==0)
  110.             {
  111.                 ans=tree[1];
  112.                 if(ans.close==0&&ans.open==0)
  113.                 cout<<"YES\n";
  114.                 else
  115.                 cout<<"NO\n";
  116.             }
  117.             else
  118.             update_tree(1,0,n-1,k-1);
  119.         }
  120.     }
  121.     return 0;
  122. }
  123.  
Runtime error #stdin #stdout #stderr 0s 80768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/XYLZUv
language:
C++14 (gcc 8.3)
created:
5 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!