HackerEarth Flipping Brackets problem solution

YASH PAL,
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

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
#endif

long 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;
}
coding problems