fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. void buildTree(string str,ll s,ll e,vector<pair<pair<ll,ll>,bool>>&tree,ll i)
  5. {
  6.     if(s==e)
  7.     {
  8.         pair<ll,ll>p1;
  9.         if(str[s]=='(')       
  10.             p1=make_pair(1,0);
  11.         else
  12.             p1=make_pair(0,1);
  13.         pair<pair<ll,ll>,bool>p=make_pair(p1,false);
  14.         tree[i]=p;
  15.         return;
  16.     }
  17.     ll mid=s+(e-s)/2;
  18.     buildTree(str,s,mid,tree,2*i);
  19.     buildTree(str,mid+1,e,tree,2*i+1);
  20.     ll toa=tree[2*i].first.first;
  21.     ll tca=tree[2*i].first.second;
  22.     ll tob=tree[2*i+1].first.first;
  23.     ll tcb=tree[2*i+1].first.second;
  24.     bool b=(toa+tob==tca+tcb)?true:false;
  25.     pair<ll,ll>pbar=make_pair(toa+tob,tca+tcb);
  26.     pair<pair<ll,ll>,bool>pdash=make_pair(pbar,b);
  27.     tree[i]=pdash;
  28.     return;
  29. }
  30. void update(string str,vector<pair<pair<ll,ll>,bool>>&tree,ll s,ll e,ll i,ll index)
  31. {
  32.     if(i<s || i>e)
  33.         return;
  34.     if(s==e)
  35.     {
  36.         if(str[i]==')')
  37.         {
  38.             tree[index].first.second--;
  39.             tree[index].first.first++;
  40.             if(tree[index].first.first==tree[index].first.second)
  41.                 tree[index].second=true;
  42.             else
  43.                 tree[index].second=false;
  44.         }
  45.         else
  46.         {
  47.             tree[index].first.first--;
  48.             tree[index].first.second++;
  49.             if(tree[index].first.first==tree[index].first.second)
  50.                 tree[index].second=true;
  51.             else
  52.                 tree[index].second=false;
  53.         }
  54.         return;       
  55.     }
  56.     ll mid=s+(e-s)/2;
  57.     update(str,tree,s,mid,i,2*index);
  58.     update(str,tree,mid+1,e,i,2*index+1);
  59.     ll toa=tree[2*index].first.first;
  60.     ll tca=tree[2*index].first.second;
  61.     ll tob=tree[2*index+1].first.first;
  62.     ll tcb=tree[2*index+1].first.second;
  63.     bool b=(toa+tob==tca+tcb)?true:false;
  64.     pair<ll,ll>pbar=make_pair(toa+tob,tca+tcb);
  65.     pair<pair<ll,ll>,bool>pdash=make_pair(pbar,b);
  66.     tree[index]=pdash;
  67.     return;
  68. }
  69. bool check(vector<pair<pair<ll,ll>,bool>>&tree)
  70. {
  71.     // for(int i=1;i<=13;i++)
  72.     //     cout<<i<<" "<<tree[i].first.first<<" "<<tree[i].first.second<<" "<<tree[i].second<<endl;
  73.     return tree[1].second;
  74. }
  75. int main()
  76. {   
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL); 
  79.     for(int tc=1;tc<=10;tc++)
  80.     {      
  81.         ll n;
  82.         cin>>n;
  83.         vector<pair<pair<ll,ll>,bool>>tree(4*n+1);
  84.         string s;
  85.         cin>>s;
  86.         //cout<<s<<endl;
  87.         buildTree(s,0,n-1,tree,1);        
  88.         ll m;
  89.         cin>>m;
  90.         cout<<"Test "<<tc<<":"<<endl;
  91.         while(m--)
  92.         {
  93.             ll k;
  94.             cin>>k;
  95.             if(k==0)
  96.             {
  97.                 if(check(tree))
  98.                     cout<<"YES"<<endl;
  99.                 else
  100.                     cout<<"NO"<<endl;
  101.             }
  102.             else
  103.             {
  104.                 update(s,tree,0,n-1,k-1,1);
  105.             }
  106.         }
  107.     }
  108.  
  109. }
Runtime error #stdin #stdout #stderr 0s 4264KB
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/J0o9Ja
language:
C++14 (gcc 8.3)
created:
4 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!