Contest Duration: ~ (local time)

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 2019-03-31 20:10:56+0900 C - Snuke the Wizard yuyaterada PyPy3 (2.4.0) 500 3156 Byte AC 578 ms 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