670E - Correct Bracket Sequence Editor - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define vt vector
#define vs vt<string>
#define vi vt<int>
#define vvi vt<vi>
#define vpii vt<pair<int, int>>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define sz(x) (int)(x).size()
#define all(c) c.begin(), c.end()
#define pb push_back
#define ff first
#define ss second
#define ps(x, y) fixed << setprecision(y) << x
#define ll long long
#define each(x, a) for (auto &x : a)
#define UNIQUE(a) (a).erase(unique((a).begin(), (a).end()), (a).end())

#define F_OR(i, a, b, s) for (int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__) (__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x) { return __builtin_popcountll(x); };
ll ceil(ll n, ll div) { assert(div > 0); return n >= 0 ? (n + div - 1) / div : n / div; }
void ynans(bool x) { if (x) cout << ("Yes\n"); else cout << ("No\n"); }
template <typename T> T min(const vector<T> &v) { return *min_element(v.begin(), v.end()); }
template <typename T> T max(const vector<T> &v) { return *max_element(v.begin(), v.end()); }
template <typename T> T acc(const vector<T> &v) { return accumulate(v.begin(), v.end(), T(0)); };

#define int ll
const ll linf = 1e18;
const ll MOD1 = 1e9 + 7;
const ll MOD9 = 998244353;

vvi adj;

// 0 -> left
// 1 -> right
// 2 -> parent

void solve() {
    
    int n,q,c;
    cin >> n >> q >> c;

    adj.assign(n,vi(3,-1));

    stack<int> st;
    string s;
    cin>>s;

    FOR(n) {
        if ( st.empty() )
            st.push(i);
        else if ( s[i] == ')' && s[st.top()] == '(' ) {
            int idx = st.top();
            st.pop();
            adj[idx][2] = i;
            adj[i][2] = idx;
        } else 
            st.push(i);

        if ( i!=0 )
            adj[i][0] = i-1;

        if (  i!=n-1 )
            adj[i][1] = i+1;
    }  

    c--;
    string moves;
    cin >> moves;

    set<int> valid;
    FOR(n) valid.insert(i);

    FOR(q) {
        char move = moves[i];

        if ( move == 'R' )
            c = adj[c][1];
        else if ( move == 'L' )
            c = adj[c][0];
        else {
            int left = min(c,adj[c][2]);
            int right = max(adj[c][2],c);
            
            int left_close = adj[left][0];
            int right_close = adj[right][1];

            if ( left_close != -1 )
                adj[left_close][1] = right_close;
            if ( right_close != -1 )
                adj[right_close][0] = left_close;

            int k = left;
            while ( k!=right_close ) {
                valid.erase(k);
                k = adj[k][1];
            }

            c = adj[right][1];
            if ( c == -1 )
                c = adj[left][0];

        }

    }

    if ( sz(valid) == 0 )
        return;

    c = *valid.begin();

    while(c!=-1) {
        cout << s[c];
        c = adj[c][1];
    }

}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    int n = 1;
    // cin>>n;
    
    FOR(i,0,n)
        solve();
}