➤ Problem Link : BRCKTS
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
pair<int,int> st[400001];
char arr[100001];
void build(int v, int l, int r)
{
if(l==r)
{
if(arr[l]=='(')
st[v]=mp(1,0);
else
st[v]=mp(0,1);
return ;
}
int mid=(l+r)/2;
build(2*v,l,mid);
build(2*v+1,mid+1,r);
st[v].first=st[2*v+1].first;
st[v].second=st[2*v].second;
int val=st[2*v].first - st[2*v+1].second;
if(val>0)
st[v].first+=val;
else
st[v].second+=abs(val);
}
void update(int v, int l,int r,int ind)
{
if(l==r)
{
if(st[v].first==1)
{
st[v].first=0;
st[v].second=1;
}
else
{
st[v].second=0;
st[v].first=1;
}
return;
}
int mid=(l+r)/2;
if(ind>=l && ind<=mid)
update(2*v,l,mid,ind);
else
update(2*v+1,mid+1,r,ind);
st[v].first=st[2*v+1].first;
st[v].second=st[2*v].second;
int val=st[2*v].first - st[2*v+1].second;
if(val>0)
st[v].first+=val;
else
st[v].second+=abs(val);
}
string query()
{
// cout<<st[1].first<<" "<<st[1].second<<endl;
if(st[1].first==0 && st[1].second==0)
return "YES\n";
return "NO\n";
}
int main()
{
for(int i=1;i<=10;i++)
{
int n,m,x;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
build(1,1,n);
cout<<"Test "<<i<<":\n";
cin>>m;
while(m--)
{
cin>>x;
if(x==0)
cout<<query();
else
update(1,1,n,x);
}
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.