Problem:


Score : 300 points

Problem Statement

You are given a string S of length N consisting of A, C, G and T. Answer the following Q queries:

Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does AC occurs as a substring?

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

Constraints

2 \leq N \leq 10^5

1 \leq Q \leq 10^5

S is a string of length N.

Each character in S is A, C, G or T.

1 \leq l_i < r_i \leq N

Input

Input is given from Standard Input in the following format:

N Q
S
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

8 3
ACACTACG
3 7
2 3
1 8

Sample Output 1

2
0
3

Query 1: the substring of S starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.

Query 2: the substring of S starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.

Query 3: the substring of S starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.



Sample input:
8 3
ACACTACG
3 7
2 3
1 8


Sample output:
2
0
3

Submission status: Runtime Error

Solution code:
def main():    
	N, Q = map(int, input().split())
    S = input()

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():    
  	N, Q = map(int, input().split())
    S = input()

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
I=lambda:map(int,input().split())
N,Q=I()
S=input()
L=[0]*Q
R=[0]*Q
for i in range(Q):
    L[i],R[i] = I()
m=[]
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        m += [i]
#print(m)
for i in range(Q):
    l=L[i]
    r=R[i]
    li=bisect.bisect_left(m,l-1)
    ri=bisect.bisect_left(m,r-1)
    #print(i,li,ri)
    print(ri-li-1 if m[ri-1]==r else ri-li)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
S = input()
x = [0 for i in range(N)]
T = ""
for i in range(len(S)):
    c = S[i]
    if c == 'A':
        A = True
    elif A and c == 'C':
        x[i] += 1
        A = False
    else:
        A = False
        T += c
s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = s[i]+x[i]
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    if s[l] != s[l+1]:
        print(s[r]-s[l]-1)
    else:
        print(s[r]-s[l])

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
S = input()
x = [0 for i in range(N)]
T = ""
for i in range(len(S)):
    c = S[i]
    if c == 'A':
        A = True
    elif A and c == 'C':
        x[i] += 1
        A = False
    else:
        A = False
        T += c
s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = s[i]+x[i]
print(s)
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    if s[l] != s[l+1]:
        print(s[r]-s[l]-1)
    else:
        print(s[r]-s[l])

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S=input()
for i in range(N):
  t=S[0:i+1].count("AC")
  A.append(t)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,iput().split())
s=input()
ACsuu=[0 for i in range(n)]
for i in range(1,n):
  Acsuu[i]=ACsuu[i-1]+(1 if s[i-1:i+1]=="AC" else 0)
for i in range(m):
  a,b=map(int,input().split())
  print(ACsuu[b-1]-ACsuu[a-1])

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S=input()
for i in range(N):
  A.append(S[0:i+1].count("AC"))
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])

Submission status: Runtime Error

Solution code:
N, Q = (int(i) for i in input().split())
S = input()

AC_list = [0] * (N+1)
 
val=0
for i in range(N-1):
    if(S[i+1]=="C"):
        if(S[i]=="A"):
            val +=1

    AC_list[i+1] = val
AC_list[i+2] = val

for i in range(Q):
    l, r = (int(_) for _ in input().split())
    if(S[r-1]=="A" and S[r]=="C"):
        print(AC_list[r]-AC_list[l-1]-1)
    else:
        print(AC_list[r]-AC_list[l-1])

Submission status: Runtime Error

Solution code:
n,q = map(int, input().split())
s =input()
A = [[int(j) for j in input().split()] for i in range(q)]
ls = [0] * (n+1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls[i+1]= ls[i]+1
    else:
        ls[i+1]= ls[i]

for k in range(q):
    print(ls[[k][0]-1-A[k][1]-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

def func(Str):
  if "AC" in Str:
    idx = Str.index("A")
    if Str[idx+1] == "C":
      return idx
    else:
      return func(Str[idx+2:])
  else:
    return -1

i = 0
ac_idx = []
while i<N:
  a = func(S[i:])
  if a != -1:
    ac_idx.append(a+i)
    i = a+i+2
  else:
    break
ac_idx = np.array(ac_idx)
for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(np.sum((ac_idx>=l-1)&(ac_idx<r-1)))

Submission status: Runtime Error

Solution code:
#coding: utf-8
N, Q = map(int, input().split())
S = input()
S_l = []
for i in range(len(S)):
    if S[i] == "A" and S[i+1] == "C":
        S_l.append([i+1, i+2])
for i in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for j in range(len(S_l)):
        if l <= S_l[j][0] <=r and l <= S_l[j][1] <= r:
            cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:

[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

k=1
locate=[-1]*N

for i in range (N):
    if s[i]=='A' and s[i+1]=='C':
        locate[k]=i
        k+=1

locate[k]=100000000

numL=1
numR=k-1

for i in range(Q):
    a = list(map(int, input().split()))
    L=a[0]-1
    R=a[1]-1

    for j in range(1,k):
        if L>locate[j-1] and L<=locate[j]:
            numL=j
            break
 


    for j in range(1,k):
        if R>locate[j] and R<=locate[j+1]:
            numR=j
            break
    
    
    print(numR-numL+1)

Submission status: Runtime Error

Solution code:

[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

k=1
locate=[-1]*N

for i in range (N):
    if s[i]=='A' and s[i+1]=='C':
        locate[k]=i
        k+=1

locate[k]=100000000

numL=1
numR=k-1

for i in range(Q):
    a = list(map(int, input().split()))
    L=a[0]-1
    R=a[1]-1

    for j in range(1,k):
        if L>locate[j-1] and L<=locate[j]:
            numL=j
            break
 


    for j in range(1,k):
        if R>locate[j] and R<=locate[j+1]:
            numR=j
            break
    
    
    print(numL,numR,numR-numL+1)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
2 S = input()
3 t=[0]*(N+1)
 4 for 5
6 for 7
8
i in range(N):
t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
i in range(Q):
l, r = map(int, input().split())
print(t[r-1] - t[l-1])

Submission status: Runtime Error

Solution code:
import sys
import bisect

def parse(inp):
    N,Q=map(int,next(inp).split())
    S=list(next(inp))
    
    lr=[[] for _ in range(Q)]
    
    for i in range(Q):
        lr[i]=list(map(int,next(inp).split()))
        
    return N,Q,S,lr
  
def whereAC(S):
    ACpoint=[]
    for i in range(len(S)-1):
        if(S[i]=='A' and S[i+1]=='C'):
            ACpoint.append(i)
            
    return ACpoint
  
def main(inp):
    N,Q,S,lr=inp
    ACpoint=whereAC(S)
    for i in range(Q):
        l,r=lr[i]

        le=min(bisect.bisect_left(ACpoint,l-1),len(ACpoint)-1)
        ge=min(bisect.bisect_left(ACpoint,r-3),len(ACpoint)-1)
        
        if(le==ge):
            if(ACpoint[le]>=l-1 and ACpoint[ge]<=r-2):
                print(1)
            else: print(0)
        else: print(ge-le+1)
          
main(parse(sys.stdin))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())		# 5 7
S = "_" + input()

#print(N,Q,S)

a=[0]*N+1

for i in range(1,N+1):
	s = S[i:i+2]
	a[i] = a[i-1] + (1 if s=="AC" else 0)


for q in range(1,Q+1):
	l, r = map(int, input().split())		# 5 7
	print(a[r]-a[l])

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())		# 5 7
S = "_" + input()

#print(N,Q,S)

a=[0]*N

for i in range(1,N+1):
	s = S[i:i+2]
	a[i] = a[i-1] + (1 if s=="AC" else 0)


for q in range(1,Q+1):
	l, r = map(int, input().split())		# 5 7
	print(a[r]-a[l])

Submission status: Runtime Error

Solution code:
import sys
 
stdin = sys.stdin

N,Q = map(int,input().split())
S = input()
se = [list(map(int, stdin.readline().split())) for i in range(Q)]

list_out = [0]
cnt = 0
f = 0

# AC文字列のAの位置をリストに収めた
for i in S:
  if i == 'A':
    f = 1
    list_out.append(list_out[-1])    
  elif i == 'C':
    if f == 1:
      cnt += 1
      list_out.append(cnt)
  else:
    list_out.append(list_out[-1])


# 指定した文字列範囲を含む要素数を表示
for i in se:
  print(list_out[i[1]] - list_out[i[0]])

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import itertools
import re
import sys
sys.setrecursionlimit(10000)
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        D = R - L
        totalCnt = cntAC(R-1, R, D, S, 0)
        print(totalCnt)
    return
 

def cntAC(l, r, D, S, cnt):
    global dp
    global T
    if r-l == D+1:
        return cnt
    if str(l)+str(r) not in T:
        T[str(l)+str(r)] = S[l-1:r]
        t = T[str(l)+str(r)]
    if str(l)+str(r) not in dp:
        #print(t)
        dp[str(l)+str(r)] = len(t.split('AC'))-1
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
    else:
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S=input()
num_count=[]

for i in range(1,len(S)+1):
    num=S[0:i].count('AC')
    #num_count.append(num)
print(num_count)
for j in range(Q):
    l,r=map(int,input().split())
    k=int(num_count[r-1])-int(num_count[l-1])
    print(k)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
2 S = input()
3 t = [0] * (N + 1)
4 for i in range(N):
5     t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
6 for i in range(Q):
7     l, r = map(int, input().split())
8     print(t[r-1] - t[l-1])

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import itertools
import re
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        D = R - L
        totalCnt = cntAC(R-1, R, D, S, 0)
        print(totalCnt)
    return
 

def cntAC(l, r, D, S, cnt):
    global dp
    global T
    if r-l == D+1:
        return cnt
    if str(l)+str(r) not in T:
        T[str(l)+str(r)] = S[l-1:r]
        t = T[str(l)+str(r)]
    if str(l)+str(r) not in dp:
        #print(t)
        dp[str(l)+str(r)] = len(t.split('AC'))-1
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
    else:
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
2 S = input()
3 t = [0] * (N + 1)
4 for i in range(N):
5 t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
6 for i in range(Q):
7 l, r = map(int, input().split())
8 print(t[r-1] - t[l-1])

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())

    
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

for i in range(q):
    l,r=map(int,input().split())
    print(dp[r-1]-dp[l-1])

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
s=list(str(input()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())))

l_list=[]
r_list=[0]
ctr1=0
ctr2=0
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        ctr1+=1
        l_list.append(ctr1)
        ctr2+=1
        r_list.append(ctr2)
    else:
        l_list.append(ctr1)
        r_list.append(ctr2)

for i in range(q):
    left=lr[i][0]
    right=lr[i][1]
    print(r_list[right-1]-l_list[left]+1)

Submission status: Runtime Error

Solution code:
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

for i in range(q):
    l,r=map(int,input().split())
    print(dp[r-1]-dp[l-1])

Submission status: Runtime Error

Solution code:
    # coding: UTF-8
    import sys
    #sys.setrecursionlimit(n)
    import heapq
    import re
    import bisect
    import random
    import math
    import itertools
    from collections import defaultdict, deque
    from copy import deepcopy
    from decimal import *
     
    n, q = map(int, input().split())
    s = list(input())
     
    ss = ""
    a = [0] * n
    b = [0] * n
    for i in range(n):
        if s[i] == "A":
            ss = s[i]
        elif s[i] == "C":
            ss += s[i]
        if ss == "AC":
            a[i] = a[i - 1] - 1
            b[i] += b[i - 1] + 1
            ss = ""
        else:
            if i > 0:
                a[i] = a[i - 1]
                b[i] = b[i - 1]
     
    for i in range(q):
        x, y = map(int, input().split())
        print(max(0, b[y - 1] + a[x - 1]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=input()
for i in m:
  a,b=map(int,input().split())
  lan=s[a-1:b]
  print(lan.count("AC"))

Submission status: Runtime Error

Solution code:
def nibun(arr, ans):
	left = 0
	right = len(arr)-1

	if arr[left] == ans:
		return left
	if arr[right] == ans:
		return right

	while right-left != 1:
		mid = int((right-left)/2)

		if arr[mid] < ans:
			left = mid
		elif arr[mid] > ans:
			right = mid
		else:
			return mid

	return right+1

N, Q = [int(x) for x in input().split()]
S = input()
AC_idx = [i for i in range(N-1) if S[i:i+2] == "AC"]

for _ in range(Q):
	l, r = [int(x) for x in input().split()]

	left = nibun(AC_idx, l-1)
	right = nibun(AC_idx, r-1)

	print(len(AC_idx[left:right]))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
s = input()
sMap = []
tmp = 0
count = []
L = []
R = []
for i in range(Q):
    a = list(map(int, input().split()))
    L.append(a[0])
    R.append(a[1])
    count.append(0)
dp =[]

for k in range(N-1):
    if s[k] == 'A' and s[k + 1] == 'C':
        sMap.append(1)
    else:
        sMap.append(0)

sMap.append(0)
lMap = []
rMap = []
norm = 0
for a in range(len(sMap)):
    tmp += sMap[a]
    norm += sMap[a]
    lMap.append(tmp)
tmp = 0
for b in reversed(range(len(sMap)-1)):
    tmp += sMap[a-1]
    rMap.append(tmp)
for n in range(Q):
    print(norm-lMap[L[n]]-rMap[R[n]])

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S=input()
M=[0]
F=False
if S[0]=='A': F=True
for s in S[1:]:
    if s=='A':
        F=True
        M.append(M[-1])
    elif s=='C':
        if F:
            M.append(M[-1]+1)
            F=False
    else:
        M.append(M[-1])
        F=False
        
for _ in range(Q):
    l,r=map(int,input().split())
    ans=M[r-1]
    if l>1:
        ans-=((S[l-2]=='A' and S[l-1]=='C') + M[l-2])
    print(ans)

Submission status: Runtime Error

Solution code:
jyouken = list(map(int, input().split())) 
moto=input()
aclist=[]
for i in range(len(moto)):
  if moto[i]=="A" and moto[i+1]=="C":
    aclist.append("a")
  else:
    aclist.append("n")
for h in range(jyouken[1]):
  hani = list(map(int, input().split())) 
  hajime=hani[0]-1
  owari=hani[1]-1
  kaisuu=aclist[hajime:owari].count("a")
  print(kaisuu)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())		# 5 7
S = input()

#print(N,Q,S)

L = "0 " + S.replace('AC', '1 0 ').replace('T', '0 ').replace('G', '0 ')
R = "0 " + S.replace('AC', '0 1 ').replace('T', '0 ').replace('G', '0 ')

L = list( map(int, L.split()) )	# 1 2 3 4 5 ...
R = list( map(int, R.split()) )	# 1 2 3 4 5 ...

#L = [0,1,2,3,4,5,6,7,8,9]
#R = [0,1,2,3,4,5,6,7,8,9]
#print(N,Q,S,L,R)
#print(N,Q,S)
#print("L", L)
#print("R", R)


from functools import reduce
#print( reduce(lambda x,y: x+y, L) )	#=> 10 (=sum(1,2,3,4))


for q in range(1,Q+1):
	ans=0
	l, r = map(int, input().split())		# 5 7
	
	if l!=r:
		X=L[l:l+1]
		Y=R[l+2:r+1]
		Z=X+Y+[0]
		
		ans = reduce(lambda x,y: x+y, Z)	#=> 10 (=sum(1,2,3,4))

		#print(l,r,"X=",X,"Y=",Y,"Z=",Z,ans)

	print(ans)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
s = input()
sMap = []
tmp = 0
count = []
L = []
R = []
for i in range(Q):
    a = list(map(int, input().split()))
    L.append(a[0])
    R.append(a[1])
    count.append(0)
dp =[]

for k in range(N-1):
    if s[k] == 'A' and s[k + 1] == 'C':
        sMap.append(1)
    else:
        sMap.append(0)
sMap.append(0)
lMap = []
rMap = []
norm = 0
for a in range(len(sMap)):
    tmp += sMap[a]
    norm += sMap[a]
    lMap.append(tmp)
tmp = 0
for b in range(reversed(len(sMap)-1)):
    tmp += sMap[a-1]
    rMap.append(tmp)
for n in range(Q):
    print(norm-lMap[L[n]]-rMap[R[n]])

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
S = input()

target = 'AC'
index = -1
idx = []
while True:
    index = S.find(target, index + 1)
    if index == -1:
        break
    idx.append(index+1)

max_idx = max(idx)
min_idx = min(idx)
ans = ''
for i in range(Q):
    L, R = list(map(int, input().split()))

    if (L > max_idx) or (R < min_idx):
        ans += '0\n'
    else:
        cnt = 0
        for j in idx:
            if L <= j < R:
                cnt += 1
            elif j >= R:
                break
        ans += str(cnt) + '\n'

print(ans, end='')

Submission status: Runtime Error

Solution code:
N, Q = (int(i) for i in input().split())
S = input()

AC_list = [0] * N
 
val=0
for i in range(N-1):
    if(S[i+1]=="C"):
        if(S[i]=="A"):
            val +=1

    AC_list[i] = val

for i in range(Q):
    l, r = (int(_) for _ in input().split())
    if(AC_list[r-1]==1 and S[r]=="C"):
        print(val[r-1]-1)
    else:
        print(val[r-1])

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
s1 = input()
ls = []
rs = []
for _ in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)

lr = []
for i in range(Q):
    lr.append([ls[i], rs[i], i])
    
lr_sort = sorted(lr, key=lambda x: x[1]-x[0], reverse=True)
for i in range(len(lr_sort)):
    l, r = lr_sort[i][0], lr_sort[i][1]
    if i == 0:
        s2 = s1[l-1:r]
        flag = 0
        for j in range(len(s2)-1):
            if s2[j]=='A' and s2[j+1]=='C':
                flag += 1
        lr_sort[i].append(flag)
    else:
        l_p, r_p = lr_sort[i-1][0], lr_sort[i-1][1]
        
        for j in range(min(l,l_p), max(l,l_p)):
            if s2[j]=='A' and s2[j+1]=='C':
                flag -= 1
        for j in range(min(r,r_p), max(r,r_p)):
            if s2[j]=='A' and s2[j+1]=='C':
                flag -= 1
        lr_sort[i].append(flag)

lr_sort2 = sorted(lr_sort, key=lambda x: x[2])
for ans in lr_sort2:
    print(ans[3])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
s = str(input())
for i in range(0, Q):
    l, r = map(int, input().split()) 
    pint(s[l-1:r-1].count('AC'))

Submission status: Runtime Error

Solution code:
N,Q = [int(i) for i in input().split()]
S = list(input())


q = [input().split() for _ in range(Q)]

li = []
for a,b in q:
    flag = 0
    for i in range(a,b):
        if S[i] == 'A':
            flag = 1
        if S[i] == 'C' and flag:
            li.append(i)

[print(i) for i in li]

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S=input()
l,r=[],[]
for i in range(Q):
    l0,r0=map(int,input().split())
    l.append(l0)
    r.append(r0)
c={}
for i in range(Q):
    for i in range(l[i]-1,r[i]-1):
        if (S[i]=='A') and (S[i+1]=='C'):
            c[i]=1
    d=int(c.count(1))
    print(d)

Submission status: Runtime Error

Solution code:
n, q = list(map(int,input().split()))
s = input()
l = []
for i in range(q) :
    l.append(list(map(int,input().split())))
pla = []
for i in range(len(s)) :
    if s[i] == "A" :
        if s[i+1] == "C" :
            pla.append(i)
for i in l :
    count = 0
    st = 0
    en = 0
    for j in range(len(pla)) :
        if i[0] - 1  <= pla[j] :
            st = j
            break
    for j in range(1,len(pla) - 1) :
        if pla[-j] < i[1] - 1 :
            en = len(pla) - 1
            break
    print(en-st+1)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
S = input()
t = 0
l = []
while(True):
    t = S.find("AC")
    if(t == -1):
        break
    l.push(t)
    S = S[t+2:]
    
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    for i in l:
        if(l <= i and i < r):
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
import bisect
 
n,q = na()
s = ns()
x = []
 
for r in range(len(s)):
  if s[r] == 'A':
    if s[r+1] == 'C':
      x.append(r)
 
for i in range(q):
  l,r = na()
  k = [j for j in x if j >= l-1 and j <= r-2]
  print(len(k))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
S = input()
Slis = [i for i in S]
output = []
for i in range(Q):
	l, r = map(int, input().split())
	output.append(Slr[l - 1:r].count('AC'))
for i in output:
	print(i)

Submission status: Runtime Error

Solution code:

[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

k=0
for i in range (N):
    if s[i]=='A' and s[i+1]=='C':
        locate[k]=i
        k+=1

k-=1

for j in range(Q):
    i = list(map(int, input().split()))
    L=i[0]-1
    R=i[1]-1

    low = 0
    high = k
    # t は中央番目の数
    t = int((low + high) / 2) 
    
    while (low<=high):
        if (L>locate[t-1] and L<=locate[t]):
            break
        elif (L > locate[t]):
            low = t+1
        elif (L < locate[t]):
            high = t-1
        t = int((low + high) / 2)
    
 
    numL=t
    
    
    low = 0
    high = k
    # t は中央番目の数
    t = int((low + high) / 2) 
    
    while (low<=high):
        if (R>=locate[t-1]+1 and R<locate[t]+1):
            break
        elif (R > locate[t-1]+1):
            low = t+1
        elif (R < locate[t-1]+1):
            high = t-1
        t = int((low + high) / 2)
    
    numR=t
    
    
    print(numR-numL+1)

Submission status: Runtime Error

Solution code:
nq = input().split()
n, q = int(nq[0]), int(nq[1])
s = list(input())
r_li = []
l_li = []
t_li = []
ac_li = []
for i in range(q):
    rl = input().split()
    l_li.append(int(rl[0]))
    r_li.append(int(rl[1]))
count = 0
i = 0
while True:
    if i == n:
        break
    else:
        if s[i] == "A":
            if s[i + 1] == "C":
                t_li.append(count)
                count += 1
                t_li.append(count)
                i += 2
            else:
                t_li.append(count)
                i += 1
        else:
                i += 1
                t_li.append(count)
for i in range(q):
    print(t_li[r_li[i] - 1] - t_li[l_li[i] - 1])

Submission status: Runtime Error

Solution code:
N, Q = [int(x) for x in input().split()]
S = input()
AC_idx = [i for i in range(N-1) if S[i:i+2] == "AC"]

def nibun(arr, ans):
	left = 0
	right = len(arr)-1

	if arr[left] == ans:
		return left
	if arr[right] == ans:
		return right

	while right-left != 1:
		mid = int((right-left)/2)

		if arr[mid] < ans:
			left = mid
		elif arr[mid] > ans:
			right = mid
		else:
			return mid

	return right+1


for _ in range(Q):
	l, r = [int(x) for x in input().split()]

	left = nibun(AC_idx, l-1)
	right = nibun(AC_idx, r-1)

	print(len(AC_idx[left:right]))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())		# 5 7
S = input()

#print(N,Q,S)

L = "0 " + S.replace('AC', '1 0 ').replace('T', '0 ').replace('G', '0 ')
R = "0 " + S.replace('AC', '0 1 ').replace('T', '0 ').replace('G', '0 ')

L = list( map(int, L.split()) )	# 1 2 3 4 5 ...
R = list( map(int, R.split()) )	# 1 2 3 4 5 ...

#L = [0,1,2,3,4,5,6,7,8,9]
#R = [0,1,2,3,4,5,6,7,8,9]
#print(N,Q,S,L,R)
#print(N,Q,S)
#print("L", L)
#print("R", R)


from functools import reduce
#print( reduce(lambda x,y: x+y, L) )	#=> 10 (=sum(1,2,3,4))


for q in range(1,Q+1):
	ans=0
	l, r = map(int, input().split())		# 5 7

	X=L[l:l+1]
	Y=R[l+2:r+1]
	Z=X+Y+[0]
	
	ans = reduce(lambda x,y: x+y, Z)	#=> 10 (=sum(1,2,3,4))

	#print(l,r,"X=",X,"Y=",Y,"Z=",Z,ans)

	print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
s = str(input())
for i in range(0, Q):
    l, r = map(int, input().split()) 
    pint(s[l:r].count('AC'))

Submission status: Runtime Error

Solution code:
import numpy as np
N, Q = map(int, input().split())
S = input()
L_R = np.array([input().split() for _ in range(Q)], dtype=int)
L = L_R[:,0]
R = L_R[:,1]

for l, r in zip(L, R):
    s = np.array([*S[l-1:r]])
    print(len(set((np.where(s=='A')[0]+1))&set((np.where(s=='C')[0]))))

Submission status: Runtime Error

Solution code:
N, Q = (int(x) for x in input().split())
S = input()
lr = [[0 for x in range(2)] for y in range(Q)]
for i in range(Q):
    lr[i] = [int(x) for x in input().split()]

a_loc = set()
for i in range(len(S)):
    if (S[i] == 'A') and (S[i+1] == 'C'):
        a_loc.add(i)
ans = [0] * Q

for i in range(Q):
    l,r = (lr[i][0], lr[i][1])
    num = 0
    for j in range(l-1, r-1):
        if j in a_loc:
            num += 1
    ans[i] = num

for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:

N, Q = map(int, input().split())
S = list(input())

AClist = []
counter = 0

i=1
while i < N:
    if S[i] == "C":
        if S[i-1] == "A":
            counter+=1

    AClist.append(counter)
    i+=1


while Q > 0:
    l, r = input().split()
    r = int(r) 
    l = int(l)

    if r == N:
        print(counter-AClist[l])
    else:
        print(AClist[r-1]-AClist[l])

    Q -= 1

Submission status: Runtime Error

Solution code:
n, q = input().split()
Q = int(q)
s = input()
S = list(s)

array = []
count = 0
ff = False
for i in range(len(S)):
    if len(S) < i+1:
        break
    if S[i] == 'A':
        flag = True
    elif flag == True and S[i] == 'C':
        count += 1
        array.append(-1)
        array.append(count)
        ff = True
    elif flag == True:
        array.append(0)
        array.append(0)
        flag = False
    else:
        array.append(0)

array_q = []
for q in range(Q):
    l, r = input().split()
    array_q.append([int(l), int(r)])

for arr in array_q:
    try:
        if ff != True:
            print(0)
            continue

        if len(array[arr[0]-1:arr[1]-1]) < 2:
            print(0)
            continue

        for a in array[arr[0]-1:]:
            if a == -1:
                flag = True
            elif flag == True:
                minv = a
                break

        for b in reversed(array[:arr[1]]):
            if b != 0 and b != -1:
                maxv = b
                break

        if minv == maxv and maxv != 0:
            print(1)
            
        elif maxv == 0:
            print(0)

        else:
            print(maxv - minv + 1)
            maxv = 0
            minv = 0
    except:
        print(0)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
s = input()
for i in range(q):
    tmp = s
    list_q = list(map(int, input().split()))
    tmp = tmp[list_q[0] -1:list_q[1]]
    print(tmp)
    tmp = tmp.split("AC")
    print(len(tmp) - 1)

Submission status: Runtime Error

Solution code:
inr = lambda: list(map(int, input().split()))
inn = lambda: input()
 
N,Q = inr()
S = inn()


cou  = 0
cou_list = []
for s in S:
    if s == "C":
        if flag == 1:
            cou += 1
            flag = 0
    elif s == "A":
        flag = 1
    else:
        flag = 0
    cou_list.append(cou)

for q in range(Q):
    l,r = inr()
    bubun = cou_list[r-1] - cou_list[l-1]
    print(bubun)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
s1 = input()
ls = []
rs = []
for _ in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)

lr = []
for i in range(Q):
    lr.append([ls[i], rs[i], i])
    
lr_sort = sorted(lr, key=lambda x: x[1]-x[0], reverse=True)
for i in range(len(lr_sort)):
    l, r = lr_sort[i][0], lr_sort[i][1]
    #print(l, r)
    if i == 0:
        s2 = s1[l-1:r]
        flag = 0
        for j in range(len(s2)-1):
            if s2[j]=='A' and s2[j+1]=='C':
                flag += 1
        lr_sort[i].append(flag)
    else:
        l_p, r_p = lr_sort[i-1][0], lr_sort[i-1][1]
        #print(l_p, r_p)
        
        for j in range(min(l,l_p), max(l,l_p)):
            if s2[j]=='A' and s2[j+1]=='C':
                flag -= 1
        for j in range(min(r,r_p), max(r,r_p)):
            if s2[j]=='A' and s2[j+1]=='C':
                flag -= 1
        lr_sort[i].append(flag)
lr_sort2 = sorted(lr_sort, key=lambda x: x[2])
for ans in lr_sort2:
    print(ans[3])