HackerEarth Flipping Brackets problem solution

In this HackerEarth Flipping Brackets problem solution A regular bracket sequence is a sequence of '(' and ')' characters defined as follows:

The empty string (without any characters) is a regular bracket sequence.
If A is a regular bracket sequence, then (A) is also considered a regular sequence.
If A and B are regular bracket sequences, then AB is also considered as a regular bracket sequence.
For a string S that consists of only '(' and ')' characters, consider a sequence of M operations that are of one of the following types:

C i: If the character Si is an opening bracket '(', then it is replaced by a closing bracket ')'. Similarly, the ')' character is replaced by the '(' character.
Q i: Determine the maximum length K of the regular bracket sequence starting at index i of the string. Formally, the string Si Si+1 ... Si+k-1 should be a regular bracket sequence, where K is maximized. If there is no regular bracket sequence starting at index i, then print 0.

HackerEarth Flipping Brackets problem solution.

`#include <bits/stdc++.h>using namespace std; #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define endl "\n"const int N=2e5+5;int n, m;string s;int pref[N], st[4*N], lazy[4*N];void build(int node, int L, int R){    if(L==R)    {        st[node]=pref[L];        return;    }    int M=(L+R)/2;    build(node*2, L, M);    build(node*2+1, M+1, R);    st[node]=min(st[node*2], st[node*2+1]);}void propagate(int node, int L, int R){       if(L!=R)    {        lazy[node*2]+=lazy[node];        lazy[node*2+1]+=lazy[node];    }    st[node]+=lazy[node];    lazy[node]=0;}int query(int node, int L, int R, int i, int j){    if(lazy[node])        propagate(node, L, R);    if(j<L || i>R)        return 1e9;    if(i<=L && R<=j)        return st[node];    int M=(L+R)/2;    int left=query(node*2, L, M, i, j);    int right=query(node*2 + 1, M+1, R, i, j);    return min(left, right);}void update(int node, int L, int R, int i, int j, int val){    if(lazy[node])        propagate(node, L, R);    if(j<L || i>R)        return;    if(i<=L && R<=j)    {        lazy[node]+=val;        propagate(node, L, R);        return;    }    int M=(L+R)/2;    update(node*2, L, M, i, j, val);    update(node*2 + 1, M+1, R, i, j, val);    st[node]=min(st[node*2], st[node*2 + 1]);}int check(int p, int idx, int mid){    int mn=query(1, 0, n, idx, mid);    return mn>=p;}int binsearch(int p, int lo, int hi){    int idx=lo;    while(lo<hi)    {        int mid=(lo+hi+1)/2;        if(check(p, idx, mid))            lo=mid;        else            hi=mid-1;    }    return lo;}int check2(int p, int idx, int mid){    int mn=query(1, 0, n, mid, n);    return mn==p;}int binsearch2(int p, int lo, int hi){    int idx=lo;    while(lo<hi)    {        int mid=(lo+hi+1)/2;        if(check2(p, idx, mid))            lo=mid;        else            hi=mid-1;    }    return lo;}int work(int idx){    int p=query(1, 0, n, idx-1, idx-1);    int mn=query(1, 0, n, idx, n);    if(mn<p)    {        int ans=binsearch(p, idx, n);        ans=ans-idx+1;        if(ans%2)            ans--;        return ans;    }    else if(mn>p)        return 0;    else    {        int ans=binsearch2(p, idx, n);        ans=ans-idx+1;        if(ans%2)            ans--;        return ans;    }}int32_t main(){    IOS;    cin>>s;    n=s.size();    for(int i=1;i<=n;i++)    {        pref[i]=pref[i-1];        if(s[i-1]=='(')            pref[i]++;        else            pref[i]--;    }    build(1, 0, n);    cin>>m;    for(int i=1;i<=m;i++)    {        char ch;        cin>>ch;        int idx;        cin>>idx;        if(ch=='C')        {            if(s[idx-1]=='(')                update(1, 0, n, idx, n, -2), s[idx-1]=')';            else                update(1, 0, n, idx, n, +2), s[idx-1]='(';        }        else            cout<<work(idx)<<endl;    }    return 0;}`

Second solution

`#ifndef _GLIBCXX_NO_ASSERT#include <cassert>#endif#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#if __cplusplus >= 201103L#include <ccomplex>#include <cfenv>#include <cinttypes>#include <cstdbool>#include <cstdint>#include <ctgmath>#include <cwchar>#include <cwctype>#endif// C++#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#endif#define ll          long long#define pb          push_back#define mp          make_pair#define pii         pair<int,int>#define vi          vector<int>#define all(a)      (a).begin(),(a).end()#define F           first#define S           second#define sz(x)       (int)x.size()#define hell        1000000007#define endl        '\n'#define rep(i,a,b)  for(int i=a;i<b;i++)using namespace std;string to_string(string s) {    return '"' + s + '"';}string to_string(const char* s) {    return to_string((string) s);}string to_string(bool b) {    return (b ? "true" : "false");}string to_string(char ch) {    return string("'")+ch+string("'");}template <typename A, typename B>string to_string(pair<A, B> p) {    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <class InputIterator>string to_string (InputIterator first, InputIterator last) {    bool start = true;    string res = "{";    while (first!=last) {        if (!start) {            res += ", ";        }        start = false;        res += to_string(*first);        ++first;    }    res += "}";    return res;}template <typename A>string to_string(A v) {    bool first = true;    string res = "{";    for (const auto &x : v) {        if (!first) {            res += ", ";        }        first = false;        res += to_string(x);    }    res += "}";    return res;}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {    cerr << " " << to_string(H);    debug_out(T...);}template <typename A, typename B>istream& operator>>(istream& input,pair<A,B>& x){    input>>x.F>>x.S;    return input;}template <typename A>istream& operator>>(istream& input,vector<A>& x){    for(auto& i:x)        input>>i;    return input;}#ifdef PRINTERS#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endiflong long readInt(long long l,long long r,char endd){    long long x=0;    int cnt=0;    int fi=-1;    bool is_neg=false;    while(true){        char g=getchar();        if(g=='-'){            assert(fi==-1);            is_neg=true;            continue;        }        if('0'<=g && g<='9'){            x*=10;            x+=g-'0';            if(cnt==0){                fi=g-'0';            }            cnt++;            assert(fi!=0 || cnt==1);            assert(fi!=0 || is_neg==false);            assert(!(cnt>19 || ( cnt==19 && fi>1) ));        } else if(g==endd){            assert(cnt>0);            if(is_neg){                x= -x;            }            assert(l<=x && x<=r);            return x;        } else {            debug(int(g));            assert(false);        }    }}string readString(int l,int r,char endd){    string ret="";    int cnt=0;    while(true){        char g=getchar();        if(g==endd){            break;        }        else if(g==')' or g=='('){            cnt++;            ret+=g;        }        else{            assert(false);        }    }    assert(l<=cnt && cnt<=r);    return ret;}long long readIntSp(long long l,long long r){    return readInt(l,r,' ');}long long readIntLn(long long l,long long r){    return readInt(l,r,'\n');}string readStringLn(int l,int r){    return readString(l,r,'\n');}string readStringSp(int l,int r){    return readString(l,r,' ');}int segtree[1<<22];int lazy[1<<22];void build(vi& arr,int pos,int l,int r){    if(l==r){        segtree[pos]=arr[l];        return;    }    else{        int mid = (l+r)/2;        build(arr,pos*2+1,l,mid);        build(arr,pos*2+2,mid+1,r);        segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);    }}void update(int pos,int l,int r,int a,int b,int val){    if(lazy[pos]){        segtree[pos]+=lazy[pos];        if(l!=r){            lazy[pos*2+1]+=lazy[pos];            lazy[pos*2+2]+=lazy[pos];        }        lazy[pos]=0;    }    if(a>r or b<l) return;    if(a<=l and r<=b){        segtree[pos]+=val;        if(l!=r){            lazy[pos*2+1]+=val;            lazy[pos*2+2]+=val;        }        return;    }    int mid = (l+r)/2;    update(pos*2+1,l,mid,a,b,val);    update(pos*2+2,mid+1,r,a,b,val);    segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);}int query(int pos,int l,int r,int a,int b){    if(lazy[pos]){        segtree[pos]+=lazy[pos];        if(l!=r){            lazy[pos*2+1]+=lazy[pos];            lazy[pos*2+2]+=lazy[pos];        }        lazy[pos]=0;    }    if(a>r or b<l) return INT_MAX;    if(a<=l and r<=b){        return segtree[pos];    }    int mid = (l+r)/2;    return min(query(pos*2+1,l,mid,a,b),query(pos*2+2,mid+1,r,a,b));}void solve(){    string s=readStringLn(1,200000);    int N = int(s.size());    assert(all_of(all(s),[](char ch){return ch==')' or ch=='(';}));    vi prefix_sum(N);    int cursum = 0;    for(int i = 0; i < N; i++){        cursum += (s[i] == '(' ? 1 : -1);        prefix_sum[i] = cursum;    }    debug(prefix_sum);    build(prefix_sum,0,0,N-1);    int M = readIntLn(1,200000);    for(int i = 0; i < M; i++){        char ch;        ch = getchar();        assert(ch=='C' or ch=='Q');        if(ch == 'C'){            ch = getchar();            assert(ch == ' ');            int idx;            if(i+1 == M) idx = readInt(1,N,EOF);            else idx = readIntLn(1,N);            idx--;            if(s[idx] == ')'){                s[idx] = '(';                update(0,0,N-1,idx,N-1,2);            }            else{                s[idx] = ')';                update(0,0,N-1,idx,N-1,-2);            }        }        else{            ch = getchar();            assert(ch == ' ');            int idx;            if(i+1 == M) idx = readInt(1,N,EOF);            else idx = readIntLn(1,N);            idx--;            int zero = idx ? query(0,0,N-1,idx-1,idx-1) : 0;            debug(zero);            int mina = idx-1;            int maxa = N;            while(maxa - mina > 1){                int mid = mina + (maxa - mina)/2;                if(query(0,0,N-1,idx,mid) < zero) maxa = mid;                else mina = mid;            }            if(maxa != N){                cout << (maxa - idx) << endl;            }            else{                mina = idx-1;                maxa = N;                while(maxa - mina > 1){                    int mid = mina + (maxa - mina)/2;                    if(query(0,0,N-1,mid,N-1) == zero) mina = mid;                    else maxa = mid;                }                cout << mina - idx + 1 << endl;            }        }    }}int main(){    ios_base::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int t=1;//  cin>>t;    while(t--){        solve();    }    return 0;}`