Problem p03081 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap
    


@mt
def slv(N, Q, S, TD):
    def reachable(i):
        if i < 0:
            return -1
        elif i >= N:
            return 1
        for t, d in TD:
            if S[i] == t:
                if d == 'L':
                    i -= 1
                else:
                    i += 1
            if i == -1:
                return -1
            elif i == N:
                return 1
        return 0
    ans = N
    lo = 0
    hi = N
    while lo < hi:
        mid = (lo+hi)//2
        if reachable(mid) < 0: lo = mid+1
        else: hi = mid
    ans -= lo


    lo = 0
    hi = N
    while lo < hi:
        mid = (lo+hi)//2
        if 0 < reachable(mid): hi = mid
        else: lo = mid+1
    ans -= N - lo
    return ans



def main():
    N, Q = read_int_n()
    S = read_str()
    TD = [read_str_n() for _ in range(Q)]
    print(slv(N, Q, S, TD))



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv_(N, Q, S, TD):
    B = [[i] for i in range(N)]
    B.append([])
    B.append([])
    S += "lr"

    TBI = defaultdict(list)
    for i, c in enumerate(S):
        TBI[c].append(i)
    for t, d in TD:
        for i in TBI[t]:
            di = 1 if d == 'R' else -1
            B[i+di].extend(B[i])
            B[i] = []
        
        print('-------------', t, d)
        for i, r in enumerate(B):
            print(i, S[i], r)
    
    for i, r in enumerate(B):
        print(i, r)

    ans = N - len(B[-1]) - len(B[N])
    return ans


@mt
def slv(N, Q, S, TD):

    # L
    f = False
    i = 0
    lmi = 0
    for t, d in reversed(TD):
        if not f and t == S[0] and d == 'L':
            f = True
            i = 1
        elif f and t == S[i] and d == 'L':
            i += 1
        if i >= N:
            break
    else:
        lmi = max(lmi, i)

    # R
    f = False
    i = N
    rmi = N  - 1
    for t, d in reversed(TD):
        if not f and t  == S[N-1] and d == 'R':
            f = True
            i = N-2
        elif f and t == S[i] and d == 'R':
            i -= 1
        if i < 0:
            break
    else:
        rmi = min(rmi, i)

    ans = N - lmi - (N-rmi-1)
    if ans < 0:
        ans = 0
    return ans


def main():
    # N, Q = read_int_n()
    # S = read_str()
    # TD = [read_str_n() for _ in range(Q)]
    # print(slv(N, Q, S, TD))

    AL ='ABCDEFGHIJKLMNOPQRSTUWXYZ'
    N = 2*(10**5)
    Q = 2*(10**5)
    S = random.choices(AL, k=N)
    TD = [(random.choice(AL), random.choice('LR')) for _ in range(Q)]
    print(slv(N, Q, S, TD))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv_(N, Q, S, TD):
    B = [[i] for i in range(N)]
    B.append([])
    B.append([])
    S += "lr"

    TBI = defaultdict(list)
    for i, c in enumerate(S):
        TBI[c].append(i)
    for t, d in TD:
        for i in TBI[t]:
            di = 1 if d == 'R' else -1
            B[i+di].extend(B[i])
            B[i] = []
        
        print('-------------', t, d)
        for i, r in enumerate(B):
            print(i, S[i], r)
    
    for i, r in enumerate(B):
        print(i, r)

    ans = N - len(B[-1]) - len(B[N])
    return ans


@mt
def slv(N, Q, S, TD):

    # L
    f = False
    i = 0
    lmi = 0
    for t, d in reversed(TD):
        if not f and t == S[0] and d == 'L':
            f = True
            i = 1
        elif f and t == S[i] and d == 'L':
            i += 1
    else:
        lmi = max(lmi, i)

    # R
    f = False
    i = N
    rmi = N  - 1
    for t, d in reversed(TD):
        if not f and t  == S[N-1] and d == 'R':
            f = True
            i = N-2
        elif f and t == S[i] and d == 'R':
            i -= 1
    else:
        rmi = min(rmi, i)

    ans = N - lmi - (N-rmi-1)
    return ans


def main():
    N, Q = read_int_n()
    S = read_str()
    TD = [read_str_n() for _ in range(Q)]
    print(slv(N, Q, S, TD))

    # AL ='ABCDEFGHIJKLMNOPQRSTUWXYZ'
    # N = 2*(10**5)
    # Q = 2*(10**5)
    # S = random.choices(AL, k=N)
    # TD = [(random.choice(AL), random.choice('LR')) for _ in range(Q)]
    # print(slv(N, Q, S, TD))


if __name__ == '__main__':
    main()