Submission #4786891


Source Code Expand

Copy
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
s = input()
TD = []
T, D = [], []
for i in range(Q):
    t,d = LS()
    TD.append([t,d])

def get_mid(lb, ub):
    if lb + ub < 0:
        return 0
    else:
        return (lb + ub) // 2
# 左から落ちるものの探索
# 2回midが同じならやめる
def find_left_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] == s[mid]:
                if td[1] == "L":
                    mid -= 1
                else:
                    mid += 1

                if mid == -1:
                    # 左に落ちた
                    lb = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid+1
                    break
                
                if mid == N:
                    # 右に落ちた
                    ub = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid
                    break
        else:
            # 落ちなかった
            ub = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid

def find_right_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] != s[mid]:
                continue

            if td[1] == "L":
                mid -= 1
            else:
                mid += 1

            if mid == -1:
                # 左に落ちた
                lb = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid+1
            
            if mid == N:
                # 右に落ちた
                ub = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid
                break
        else:
            # 落ちなかった
            lb = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid + 1

left_survived = find_left_dropped()
#  print(left_survived)
right_survived = find_right_dropped()
#  print(right_survived)

result = right_survived - left_survived
print(result)

Submission Info

Submission Time
Task C - Snuke the Wizard
User yuyaterada
Language PyPy3 (2.4.0)
Score 500
Code Size 3156 Byte
Status
Exec Time 578 ms
Memory 104924 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 500 / 500 sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt
Case Name Status Exec Time Memory
sample_01.txt 344 ms 67948 KB
sample_02.txt 272 ms 64236 KB
sample_03.txt 274 ms 64236 KB
test_01.txt 526 ms 104268 KB
test_02.txt 521 ms 104140 KB
test_03.txt 546 ms 104908 KB
test_04.txt 577 ms 104800 KB
test_05.txt 573 ms 104620 KB
test_06.txt 566 ms 104524 KB
test_07.txt 567 ms 104700 KB
test_08.txt 564 ms 104696 KB
test_09.txt 522 ms 104612 KB
test_10.txt 514 ms 104492 KB
test_11.txt 521 ms 104716 KB
test_12.txt 491 ms 104836 KB
test_13.txt 505 ms 104836 KB
test_14.txt 517 ms 104788 KB
test_15.txt 530 ms 104924 KB
test_16.txt 509 ms 104784 KB
test_17.txt 555 ms 104140 KB
test_18.txt 480 ms 94932 KB
test_19.txt 578 ms 104908 KB
test_20.txt 533 ms 98908 KB
test_21.txt 562 ms 104908 KB
test_22.txt 504 ms 99376 KB
test_23.txt 505 ms 104908 KB
test_24.txt 477 ms 102892 KB
test_25.txt 462 ms 98512 KB
test_26.txt 381 ms 83128 KB