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: Time Limit Exceeded

Solution code:
import numpy as np
N, Q = map(int, input().split())
S = input()
po =[]
while True:
    if S.find("AC") == -1:
        break
    else:
        po.append(S.find("AC"))
        S =S.replace("AC","XX",1)
po_numpy = np.array(po)    
for i in range(Q):
    l1 ,r1 = map(int, input().split())
    print(np.sum(np.logical_and(l1-1<= po_numpy, po_numpy <= r1-2)))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = input()
z = []
for j in range(N-1):
  if S[j] =='A' and S[j+1]=='C':
    z.append(j+1)
for i in range(Q):
  l,r = map(int,input().split())
  if r-l >= 1:
    if r-l == 1:
      if l in z:
        print('1')
      else:
        print('0')
    else:
      ans = [x for x in z if x >= l and x<= r-1]
      print(len(ans))
  else:
    print('0')

Submission status: Time Limit Exceeded

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

for i in range(int(Q)):
    list.append(int(x) for x in input().split())

for i in range(int(Q)):
    a, b = list[i]
    sss = S[a - 1:b]
    count = sss.count("AC")
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
NQ = input().split(" ")
S = str(input())
N = int(NQ[0])
Q = int(NQ[1])
result_list = []
l = 0
r = 0
lr = ""
for i in range(0, Q):
  lr = input().split(" ")
  l = int(lr[0])
  r = int(lr[1])
  subStr_S = S[l-1:r]
  print(subStr_S.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
char_numbers = [int(e) for e in input().split(" ")]

char = input()

questions = []
for i in range(char_numbers[1]):
    questions.append([int(e) - 1 for e in input().split()])

start = [0]

while 1:
    start.append(char.find("AC",start[-1]))
    if start[-1] == -1:
        start[-2] -= 2
        del start[0]
        del start[-1]
        break
    else:
        start[-1] = start[-1] + 2
        start[-2] -= 2 
for i in questions:
    n = sum(x>=i[0] and x+1 <= i[1] for x in start)
    print(n)

Submission status: Time Limit Exceeded

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

flag=0
for i in range((N+1)//2):
    if S[i*2]=='A':
        if i*2!=len(S)-1:
            if S[(i*2)+1]=='C': count_list.append(i*2+1)
    elif S[i*2]=='C':
        if i*2!=0:
            if S[(i*2)-1]=='A': count_list.append(i*2)

for i in range(Q):
    l,r=map(int,input().split())
    l,r=l-1,r-1 #リストのインデックスとの整合
    n=sum(l+1<=x<= r for x in count_list)
    print(max(n,0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]
ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]

for i in range(Q):
    ans = sum(ac_tf_list[lr_list[i][0]-1:lr_list[i][1]-1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
l = []
r = []
n,q = input().split()
N = int(n)
Q = int(q)
S = input()
for i in range(Q):
    L,R = input().split()
    l.append(int(L)-1)
    r.append(int(R)-1)
flag = [0 for i in S]
for i in range(len(S)-1):
    if((S[i] == "A")&(S[i+1] == "C")):
        flag[i] = 1
for j in range(Q):
    count = 0
    for i in range(l[j],r[j]):
        count = count + flag[i]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()

s_count_t = s.count("AC")

for _ in range(q):
    l, r = map(int, input().split())
    s_count_before = s[:l].count("AC")
    s_count_after = s[r - 1:].count("AC")
    print(s_count_t - s_count_before - s_count_after)

Submission status: Time Limit Exceeded

Solution code:
import collections

N, Q = map(int, input().split())
S = input()
li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append(S[l-1:r])

for j in range(Q):
    print(li[j].count('AC'))

Submission status: Time Limit Exceeded

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(N):
    c.append(0)
for i in range(N-1):
    if (S[i]=='A') and (S[i+1]=='C'):
        c[i]+=1
for i in range(Q):
    d=c[l[i]-1:r[i]-1]
    print(d.count(1))

Submission status: Time Limit Exceeded

Solution code:
input_list = input().split()
n = int(input_list[0])
q = int(input_list[1])
s = input()

for i in range(q):
  input_list = input().split()
  l = int(input_list[0])
  r = int(input_list[1])
  
  target = s[l-1:r]
  
  counter = 0
  for j in range(r-l):
    if target[j:j+2] == 'AC':
      counter += 1
  print(counter)
  counter = 0

Submission status: Time Limit Exceeded

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

for q in range(Q):
	a ,b = map(int , input().split())
	l.append(a)
	r.append(b)

for q in range(Q):
	count = 0
	a = l.pop(0)
	b = r.pop(0)
	subS = S[a-1:b]
	while subS!= "":
		x = subS.find("A")
		if x!= -1:
			subS = subS[x:]
		else:
			break
		if len(subS) <= 1:
			break
		if subS[1] == "C":
			count += 1
			subS = subS[2:]
#			print("subS = " + subS)
		else:
			subS = subS[1:]
#			print("subS = " + subS)
	print(count)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
S = s[1]
for i in s[2:]:
    a, b = map(int, i.split())
    print(len(re.findall("AC", S[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
num_mid=0
for k in range(Q):
    l,r=map(int,input().split())
    #for i in range(l-1,r):
#    S_slice=S[l-1:r]
    mid=int(((l-1)+(r-1))/2)
    #print(mid)
    num_l=S[l-1:mid].count('AC')
    num_r=S[mid+1:r].count('AC')
    if (S[mid-1]=='A'and S[mid]=='C') and (mid)!=(l-1):
        #print(S[mid],mid)
        num_mid=1
    #print(num_l,num_r,num_mid)
    print(num_l+num_r+num_mid)
    num_mid=0

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()

import re

pattern = r"AC+"
repatter = re.compile(pattern)

result = []
for _ in range(q):
    begin, end = map(int, input().split())
    target_str = s[begin - 1:end]
    result.append(str(len(repatter.findall(target_str))))

print("\n".join(result))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())
    S = input()
    inlist = [map(int, input().split()) for i in range(Q)]
    index_list = []
    for i in range(N):
        if S[i:i+2] == 'AC':
            index_list.append(i+1)

    for start, stop in inlist:
        cnt = 0
        for i in index_list:
            if start <= i and i+1 <= stop:
                cnt += 1
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count("AC"))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import re
N, Q = (int(i) for i in input().split())
s = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]
ms = re.finditer("AC", s)
ml = list(ms)
for i in range(Q):
    count = 0
    for j in range(len(ml)):
        a, b = ml[j].span()
        #print(a, b)
        #print("q", lr[i])
        if lr[i][0]-1 <= a and b <= lr[i][1]:
            count = count +1
            #print("counted")

    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
bef = ''
pos = []
for idx,val in enumerate(S):
    if val == 'C' and bef == 'A':
        pos.append((idx -1) * 10 + idx)
    bef = val

cnt = 0
for i in range(Q):
    min_v = (lr[i][0] - 1) * 10 + lr[i][0]
    max_v = (lr[i][1] - 2) * 10 + (lr[i][1] - 1)
    n = sum(1 for x in pos if x >= min_v and x <= max_v)
    print(n)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()
ls=""
for a in range(n-1):
  tmp=s[a:a+2]
  if tmp=="AC":
    ls+="#"
  else:
    ls+="."
for que in range(q):
  l,r=map(int,input().split())
  tmp=ls[l-1:r-1]
  print(len(tmp.replace(".","")))

Submission status: Time Limit Exceeded

Solution code:
import re
N, Q = map(int, input().split())
S = input()
 
def AC_counter(l, r):
    tmp = S[l-1:r]
    match = re.findall('AC', tmp)
    print(len(match))
 
for _ in range(Q):
    l, r = map(int, input().split())
    AC_counter(l, r)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()
e=[]
for j in range(n-1):
    if s[j:j+2]=="AC":
        e.append(1)
    else :
        e.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]
for q in range(Q):
    ans = 0
    flag = False
    for a in S[lr[q][0]:lr[q][1]]:
        if a == 'A':
            flag = True
        elif a == 'C':
            ans += 1
            flag = False
        else:
            flag = False
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import re
n, q = map(int, input().split())
s = input()
 
for _ in range(q):
  a, b = map(int, input().split())
  print(len(re.findall("AC",s[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
import re
n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()


for i in range(Q):
    lr = input().split()
    tmp = S[int(lr[0])-1:int(lr[1])]
    count = len(re.findall('AC', tmp))
    print(str(count))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
s = input()

ac_positions = []
for i in range(n):
    if s[i:i + 2] == 'AC':
        ac_positions.append(i + 1)

questions = []
for i in range(q):
    question = list(map(int, input().split()))


# for question in questions:
    ac_count = 0

    explore_ac_positions = ac_positions[
                           bisect.bisect_left(ac_positions, question[0]):
                           bisect.bisect_right(ac_positions, question[1] - 1)]

    ac_count = len(explore_ac_positions)
    # for ac_position in explore_ac_positions:
    #     if question[0] <= ac_position and ac_position + 1 <= question[1]:
    #         ac_count += 1

    print(ac_count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import re

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

array = []

for m in re.finditer(r'AC', S):
    array.append(m.start())


for i in range(Q) :
    count = 0
    for j in range(len(array)) :
        if L[i][0] - 1 <= array[j] and L[i][1] - 2 >= array[j] :
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
jyouken = list(map(int, input().split())) 
moto=input()
for h in range(jyouken[1]):
  hani = list(map(int, input().split())) 
  count=0
  for i in range(hani[0]-1,hani[1]-1):
    if moto[i]=="A" and moto[i+1]=="C":
      count=count+1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n,q = (int(i) for i in input().split())  
s = input()
for i in range(q):
    li,ri = (int(x) for x in input().split())
    print(s[li-1:ri].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
import re

n, q = map(int, input().split())
s = input()
l = []
r = []
for i in range(q):
    ll, rr = map(int, input().split())
    l.append(ll)
    r.append(rr)

for i in range(q):
    temp = s[l[i]-1:r[i]].replace("AC", "ac")
    temp = re.sub('[A-Z]', " ", temp)
    temp_list = temp.split("c")
    print(len(temp_list)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n, q = map(int, input().rstrip().split())
s = input().rstrip()
lr = (tuple(map(int, input().rstrip().split())) for _ in range(q))
dp = [[0]*len(s) for _ in range(len(s))]

for now in lr:
    l, r = now[0]-1, now[1]
    used = dp[l][r-1]
    if used == 0:
        tmp = s[l:r]
        count = tmp.count('AC')
        print(count)
        dp[l][r-1] = count
    else:
        print(used)

Submission status: Time Limit Exceeded

Solution code:
_, q = input().split()
s = input()
qs = [list(map(int, input().split())) for _ in range(int(q))]

# def get_num_AC(ccond, s, count):
#     if s == []:
#         return count
#     if ccond:
#         if s.pop() == 'A':
#             return get_num_AC(False, s, count+1)
#         else:
#             if s == []:
#                 return count
#             else:
#                 return get_num_AC(s.pop() == 'C', s, count)
#     return get_num_AC(s.pop() == 'C', s, count)

def get_substr(s, smaller, larger):
    s1 = s[smaller-1:larger]
    return s1

for smaller, larger in qs:
    substr = get_substr(s, smaller, larger)
    count = substr.count('AC')
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()
e=[]
for j in range(n-1):
    if s[j:j+2]=="AC":
        e.append(1)
    else :
        e.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
import re
N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l, r = map(int,input().split())
    print(len(re.compile('AC').findall(S[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = input()


for i in range(q):
        t1,t2 = map(int,input().split())
        r1 =s[t1-1:t2]
        print(r1.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

lst = [0] * N
for i in range(1,N):
    if S[i] == "C" and S[i-1] == "A":
        lst[i] = 1

ans = 0
for i in range(Q):
    head,tail = map(int,input().split())
    ans = sum(lst[head:tail])
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = str(input())
cnt0 = S.count("AC")
cnt = []

for i in range(0,N):
 sli = S[i:]
 cnt1 = sli.count("AC")
 cnt.append(cnt1)

for i in range(0,Q):
 l,r = map(int,input().split())
 ans = cnt[l-1] - cnt[r-1]
 print(ans)
S

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()

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

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

for i in range(1,n):
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    l,r=map(int,input().split())
    print(dp[l-1][r-1])

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
S = s[1]
lr = list()
for i in s[2:]:
    lr.append(tuple(map(int, i.split())))
for i in lr:
    print(len(re.findall("AC", S[i[0]-1:i[1]])))

Submission status: Time Limit Exceeded

Solution code:
from re import sub

def func(start, end, word):
    result = 0
    this_word = word[start-1:end]
    #print()
    #print(this_word)
    this_word = sub('[^AC]', ' ', this_word)
    this_word = sub('AC', 'AC ', this_word).strip().split(' ')
    #print(this_word)
    for i in this_word:
        if i == 'AC':
            result += 1
    return result

config = input().strip().split(' ')
word_length = int(config[0])
question_num = int(config[1])

word = input().strip()
result = []

for i in range(question_num):
    config = input().strip().split(' ')
    start_index = int(config[0])
    end_index = int(config[1])
    ans = func(start_index, end_index, word)
    result.append(ans)

for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,Q=map(int,input().split())
    S=input()
    check=[False]*N
    i = 0
    while i < N-1:
        if S[i] == 'A' and S[i+1]=='C':
            check[i] = True
            i += 2
            continue
        i += 1

    for i in range(Q):
        start,end=map(int,input().split())
        print(check[start-1:end-1].count(True))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]

for i, sy_list in enumerate(sy):
  if i >= 2:
    l, r = map(int, sy_list.split())
    s = S[l-1:r]
    print(s.count('AC'))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = input().split()
    S = input()
    list = []

    for i in range(int(Q)):
        list.append(int(x) for x in input().split())

    for i in range(int(Q)):
        a, b = list[i]
        sss = S[a - 1:   b]
        count = sss.count("AC")
        print(count)

    return 0


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import re

N,Q = map(int, input().split())
S = input()
itr = re.finditer("AC",S)
li = [i.span() for i in itr]

for i in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for match in li:
    	if l <= int(match[0]) + 1 and int(match[1]) <= r :
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S = input()
list = [print(S[start-1:end].count("AC")) for start,end in [map(int, input().split()) for i in range(Q)]]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = map(int,input().split())
x=[]
l=[]
r=[]
t = np.zeros(Q)
S = input()
for s in S:
  x.append(s)
for i in range(Q):
  li,ri=map(int,input().split())
  ti=0
  j=0
  l.append(li)
  r.append(ri)
for j in range(max(r)-min(l)):
  if x[min(l)-1+j]=="A" and x[min(l)+j]=="C":
    for i in range(Q):
      if l[i]<=min(l)+j and r[i]>=min(l)+j+1:
        t[i]+=1
for i in range(Q):
  print(int(t[i]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [S[:j].count("AC") for j in range(1, N + 1)]

ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

N, Q = map(int, input().split())
 
S = input()
 
lr = [list(map(int, i.split())) for i in sys.stdin]

# for q in range(Q):
#  lr.append(list(map(int, input().split())))
  
for q in lr:
  st = q[0]-1
  en = q[1]
  s = S[st:en]
  print(s.count('AC'))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for i in range(Q):
    a = li[i][0]-1
    b = li[i][1]
    S_a = S[a:b]
    ans += S_a.count("AC")
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
import sys
 
stdin = sys.stdin

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

check_point = []
inf = 10 ** 18

# AC文字列のAの位置をリストに収めた
for i in range(inf):
  out = S.find('AC')
  if out < 0:
    break
  else:
    S = S[out+2:]
    check_point.extend([(out + len(check_point) * 2)])
  

# 指定した文字列範囲を含む要素数を表示
for i in range(Q):
  start, end  = map(int, stdin.readline().split())
  print(len([i for i in check_point if (start - 1 <= i) and (i + 1 < end)]))

Submission status: Time Limit Exceeded

Solution code:
N ,Q = map(int, input().split())
S = input()
    
def countAC(S, r, l):
    data = S[r-1:l]
    cnt = 0
    for i in range(0, len(data), 2):
        if data[i]=='A':
            if (i+1)<len(data):
                if data[i+1] == 'C':
                    cnt+=1
        elif data[i]=='C':
            if (i-1)>=0:
                if data[i-1] == 'A':
                    cnt+=1
    return cnt
  
ret = []

for i in range(Q):
    r, l = map(int, input().split())
    cnt = countAC(S, r, l)
    ret.append(str(cnt))
print('\n'.join(ret))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

n = [int(i) for i in input().split()]
s = input()
t = [0] *(n[0])
for i in range(n[0]-2):
    
    if s[i:i+2] == "AC":
        t[i] = 1
        i += 1
    elif s[i+1:i+2] !="A":
      if s[i+2:i+3] !="A":
        i += 2
      else:
        i +=1
        
for i in range(n[1]):
    m = [int(j) for j in input().split()]
    a = 0
    for j in range(m[0],m[1]):
        a += t[j-1]
    print(a)

Submission status: Time Limit Exceeded

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

input_list = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(S[l - 1 : r].count(target))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
lst = []
idx = 0
for x in range(len(S) - 1):
    if S[x] == 'A' and S[x + 1] == 'C':
        lst.append(1)
    else:
        lst.append(0)

for x in range(Q):
    a, b = map(int, input().split())
    print(sum(lst[a-1:b-1]))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
ls=[];rs=[]
for i in range(Q):
    l,r=map(int,input().split())
    n=0;a=False
    for k in S[(l-1):(r)]:
        if k!="A" and a==False:
            pass
        elif k=="A":
            a=True
        elif a:
            if k=="C":
                n+=1
            else:
                a=False
    print(n)

Submission status: Time Limit Exceeded

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())))
sl=[]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        sl.append([i+1,i+2])
    else:
        pass

for i in range(q):
    ctr1=1
    ctr2=0
    for k in range(len(sl)):
        if lr[i][0] > sl[k][0]:
            ctr1+=1
        if lr[i][1] >= sl[k][1]:
            ctr2+=1
        else:
            break
    print(ctr2-ctr1+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]
C = []
#"AC"が何文字目か判断
terget = "AC"
index = -1
while True:
    index = S.find(terget,index+1)
    if index == -1:
        break
    C.append(index)
    
for l,r in lr:
    AC = 0
    for j in C:
        if j >= l-1:
            if j < r-1:
                AC += 1
            else:
                break
    print(AC)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(Q):
  l[i],r[i]=map(int,input().split())
counter=[0]*N
for i in range(len(S)-1):
  if S[i]=="A":
    counter[i]=(S[i+1]=="C")
  else:counter[i]=0
for j in range(Q):
  print(sum(counter[l[j]-1:r[j]-1]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
S = input()
ac = []
for i in range(len(S)-1):
    if S[i:i+2] == 'AC':
        ac.append(i)
for _ in range(Q):
    li, ri = list(map(int, input().split()))
    li -= 1
    count = 0
    for a in ac:
        if li <= a and a+1 < ri:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

for _ in range(Q):
  l, r = map(int, input().split())
  length = r - l + 1
  print((length - len(S[l-1:r].replace("AC",""))) // 2)

Submission status: Time Limit Exceeded

Solution code:
def countAC(s):
    index = []
    for i in range(N-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                index.append(i)
                continue
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    for index in SIndex:
        if l-1 <= index < r-1:
            out += 1
    print(out)
    out = 0

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N, Q = map(int, input().split())
S = input()
for i in range(Q):
    q1, q2 = map(int, input().split())
    qs = S[q1-1: q2]
    print(qs.count("AC"))

Submission status: Time Limit Exceeded

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

for i in range(Q):
	count = 0
	l, r = map(int, input().split())
	Sr = S[l-1:r]
	print(Sr.count('AC'))

Submission status: Time Limit Exceeded

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

    for i in range(int(Q)):
        a, b = (int(x) for x in input().split())
        sss = S[a - 1: b]
        count = sss.count("AC")
        print(count)

    return 0


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
ac_numbers = 0 
for i in range(Q):
    l, r = map(int, input().split())
    for j in range(r-l): 
        if S[l-1+j:l+j+1] == 'AC':
            ac_numbers += 1
    print(ac_numbers)
    ac_numbers = 0

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    n, q = inputAsIntArr()
    s = input()

    idxes = []
    for i in range(n-1):
        if s[i] != 'A':
            continue
        if s[i+1] == 'C':
            idxes.append(i)
            i += 1

    num_acs = ""
    for i in range(q):
        li, ri = inputAsIntArr()
        num_ac = len([v for v in idxes if li-2 < v < ri-1])
        num_acs += str(num_ac) + "\n"

    print(num_acs.strip())


def inputAsIntArr():
    return [int(i) for i in input().split()]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    si2 = [n for n in si if n in ("A","C")]
    cnt = 0
    for j in range(len(si2)-1):
        if si2[j] == "A":
            if si2[j+1] == "C":
                cnt += 1
    else:
        cntli.append(cnt)

for p in cntli:
    print(p)

Submission status: Time Limit Exceeded

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())))
sl=[]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        sl.append([i+1,i+2])
    else:
        pass

for i in range(q):
    ctr1=1
    ctr2=0
    for k in range(len(sl)):
        if lr[i][0] > sl[k][0]:
            ctr1+=1
        else:
            break
    for m in range(len(sl)):
        if lr[i][1] >= sl[m][1]:
            ctr2+=1
        else:
            break
    print(ctr2-ctr1+1)

Submission status: Time Limit Exceeded

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

start_pair = []
for j in range(N-1):
    if S[j] == 'A' and S[j+1] == 'C':
        start_pair.append(j)

length = len(start_pair)
start_pair = np.asarray(start_pair)
for i in range(Q):
    if length == 0:
        print(0)
    else:
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        right = np.searchsorted(start_pair, r)
        left = np.searchsorted(start_pair, l)
        print(right-left)

Submission status: Time Limit Exceeded

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

import re
ptn = re.compile(r"AC")

for _  in range(Q):
  l, r = map(int,input().split())
  x = re.findall(ptn,S[l-1:r])
  print(len(x))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import re
from sys import stdin

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

def func(Str):
  idx = Str.find("AC")
  return idx

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()]
  L = ac_idx >= l-1
  R = ac_idx < r-1
  print(np.sum(np.logical_and(L, R)))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n)] for j in range(n)]

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

for i in range(1,n):
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = input().split()
S = input()
for i in range(int(Q)):
    str_l, str_r = input().split()
    l = int(str_l)
    r = int(str_r)
    count = 0
    for j in range(0, r - l, 1):
        if 'A' == S[j+l-1]:
            if 'C' == S[j+l]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
NQ = input().split(" ")
S = str(input())
N = int(NQ[0])
Q = int(NQ[1])
result_list = []
l = 0
r = 0
lr = ""
for i in range(0, Q):
  lr = input().split(" ")
  l = int(lr[0])
  r = int(lr[1])
  subStr_S = str(S[l-1:r]).replace("G", "").replace("T", "")
  result_list.append(subStr_S.count("AC"))

[print(result) for result in result_list]

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
s = str(input())

for _ in range(Q):
    l,r = map(int,input().split())
    print(s[l-1:r].count("AC"))