Submission #15,694

2025-02-21 18:34:57

python3

Time limit exceeded 38/50

317ms

17908 KiB

from sys import stdin, stdout
input=stdin.readline

def s():
 N,K,M=map(int,input().split())
 szobak=tuple(map(int,input().split()))
 lepesek=tuple([tuple(map(int,input().split())) for i in range(M)])

 def test(start):
  for a,b in lepesek:
   if szobak[start]==a:
    start+=b
    if start==N:
     return 1
    elif start==-1:
     return -1
  return 0

 res=0
 first=test(0)
 last=test(N-1)
 if last==1:
  if first==1:return N 
  else:
   lo=0
   hi=N-1
   while hi-lo>1:
    mid=(hi+lo)//2
    if test(mid)==1:hi=mid
    else:lo=mid
   res+=N-hi
 if first==-1:
  if last==-1:return N
  else:
   lo=0
   hi=N-1
   while hi-lo>1:
    mid=(hi+lo)//2
    if test(mid)==-1:lo=mid
    else:hi=mid
   res+=hi
 return res

stdout.write(str(s())+'\n')

	Sum	Test	Verdict		Time	Memory
base	38/50
		1	Accepted	0/0	16ms	3308 KiB
		2	Accepted	0/0	298ms	17908 KiB
		3	Accepted	1/1	17ms	3108 KiB
		4	Accepted	1/1	17ms	3124 KiB
		5	Accepted	1/1	17ms	3120 KiB
		6	Accepted	1/1	17ms	3268 KiB
		7	Accepted	1/1	17ms	3308 KiB
		8	Accepted	1/1	17ms	3316 KiB
		9	Accepted	1/1	18ms	3124 KiB
		10	Accepted	1/1	18ms	3376 KiB
		11	Accepted	1/1	17ms	3268 KiB
		12	Accepted	1/1	19ms	3352 KiB
		13	Accepted	1/1	37ms	4080 KiB
		14	Accepted	1/1	23ms	3632 KiB
		15	Accepted	1/1	21ms	3756 KiB
		16	Accepted	1/1	35ms	4100 KiB
		17	Accepted	1/1	39ms	4404 KiB
		18	Accepted	1/1	39ms	4352 KiB
		19	Accepted	1/1	146ms	14676 KiB
		20	Accepted	1/1	289ms	17876 KiB
		21	Accepted	1/1	186ms	14676 KiB
		22	Accepted	1/1	216ms	14676 KiB
		23	Accepted	1/1	272ms	16568 KiB
		24	Accepted	1/1	289ms	17664 KiB
		25	Accepted	1/1	284ms	17664 KiB
		26	Accepted	1/1	291ms	17668 KiB
		27	Accepted	3/3	246ms	14900 KiB
		28	Time limit exceeded	0/3	314ms	14904 KiB
		29	Accepted	3/3	252ms	15048 KiB
		30	Time limit exceeded	0/3	303ms	14852 KiB
		31	Time limit exceeded	0/3	303ms	14900 KiB
		32	Time limit exceeded	0/3	317ms	14900 KiB
		33	Accepted	4/4	155ms	9188 KiB
		34	Accepted	4/4	273ms	14252 KiB