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:
N,Q=map(int,input().split())
S=list(input())
count_list=[]

flag=0
for i in range((len(S)+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()
b = []
tmp = 0
while True:
    tmp = s.find("AC", tmp)
    if tmp == -1:
        break
    tmp += 1
    b.append(tmp)
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(sum(l <= x < r for x in b))
print(*ans, sep="\n")

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=[]
for i in range(len(S)-1):
  if S[i]=="A":
    counter.append((S[i+1]=="C"))
  else:counter.append(0)
for j in range(Q):
  print(sum(counter[l[j]-1:r[j]-1]))

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
    
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:
import numpy as np;
count = 0;
maxnum=0;
n,m = input().split();
mark=np.zeros(int(n));
s = input();

for j in range(len(s)):
    for i in range(int(n)-1):
        if(s[i]=='A' and s[i+1] == 'C'):
            mark[i] = 1;
for j in range(int(m)): 
    x,y = input().split();
    print(int(np.sum(mark[(int(x)-1):int(y)-1])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
s = input()
a = [0 for i in range(q)]
for k in range(q):
    i,j = map(int, input().split())
    print(s[i-1:j].count("AC"))

Submission status: Time Limit Exceeded

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())
	ACkazu = 0
	for j in range(l, r):
		if Slis[j - 1] == 'A' and Slis[j] == 'C':
			ACkazu += 1
	output.append(ACkazu)
for i in output:
	print(i)

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 = []

for i in range(0, Q):
  lr = input().split(" ")
  l = int(lr[0])
  r = int(lr[1])
  subStr_S = str(S[l-1:r])
  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 = input()
e = [[int(i) for i in input().split()] for i in range(q)]
for m in range(q):
  lim = s[e[m][0]-1:e[m][1]]
  print(lim.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
flag = [0, 0]
for i in range(N-1):
	if S[i] == 'A' and S[i+1] == 'C':
		flag.append(1)
	else:
		flag.append(0)
# print(flag)
ans = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
	for j in range(1,N+1):
		ans.append(0)
		
for i in range(N):
	for j in range(N):
		ans[i][j+1] = ans[i][j] + flag[j+1]
		ans[i+1][j] = ans[i][j] - flag[i+1]

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,Q = map(int, input().split())
S = input()
SS = S[1:]+"0"
fl = [None] * N
for n in range(N-1):
    if S[n]+SS[n] == "AC":
        fl[n] =1
    else:
        fl[n] =0

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

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]
	j = 0
	while (j < (len(Sr)-1)):
		if(Sr[j] == 'A' and Sr[j+1] == 'C'):
			count += 1
			j += 1
		elif(Sr[j+1] != 'A'):
			j += 1
		elif(j+2!=len(Sr) and Sr[j+2] != 'C'):
			j += 2
		j += 1
	print(count)

Submission status: Time Limit Exceeded

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

a = [0] * Q
b = [0] * Q
for i in range(Q):
    a[i], b[i]= map(int, input().split())

for i in range(Q):
    seq = S[a[i]-1:b[i]]
    seq2 = seq.replace("AC","")
    print(int((len(seq) - len(seq2)) / 2))

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 S!= "":
		while subS[0] != "A":
			subS = subS[1:]
#			print("subS = " + subS)
			if subS =="":
				break
		if len(subS) <= 1:
			break
		elif subS[1] == "C":
			count += 1
			subS = subS[2:]
#			print("subS = " + subS)
		else:
			subS = subS[1:]
#			print("subS = " + subS)
		if subS == "":
			break
	print(count)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
raw_list = list(input())
AC_pos = []
for idx,char in enumerate(raw_list):

    if raw_list[idx] =="A":
        if idx == len(raw_list)-1:
            break
        if raw_list[idx+1] == "C":
            AC_pos.append(idx)
#print(AC_pos)
for i in range(q):
    li, ri = map(int,input().split())
    print(sum(li-1<=x<=ri-2 for x in AC_pos))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

N, Q = map(int, sys.stdin.readline().split())
S = input()
s = []
l = []
r = []

for i in range(Q):
    l0, r0 = map(int, sys.stdin.readline().split())
    l.append(l0)
    r.append(r0)

for j in range(Q):
    print(S[l[j]-1:r[j]].count('AC'))

Submission status: Time Limit Exceeded

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

count=[]
for i in range(len(s)):
	count.append(0)

for i in range(len(s)-1):
	if s[i] == "A" and s[i+1] == "C":
		count[i]=count[i]+1
		#count[i+1]=count[i+1]+1
#print(count)

result=0
for i in range(Q):
	l, r = map(int,input().split())
	for i in count[l-1:r-1]:
		#if count[i]==1 and count[i+1]==0:
 			result = result+i
	print(result)
	result=0

Submission status: Time Limit Exceeded

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

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

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

    return 0


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

lia = [1 if s == 'A' else 0 for s in S]
lis = [1 if s == 'C' else 0 for s in S]
liac = [a * c for a, c in zip (lia[:-1], lis[1:])]

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = list(input())
#S  = input()
#s = []
s = [0 for i in range(Q)]
#print(s)
for i in range(Q):
    l,r = map(int,input().split())
    #s.append(0)
    j = l-1
    while j < r-1:
    #for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            s[i] += 1
            j += 1
        j += 1
for i in range(Q):
    print(s[i])
#for i in range(Q):
#    print(S[i].count("AC"))

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+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=0:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    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()

ans = []
for i in range(N):
    s_ = S[i:]
    tmp_ans = []
    for j in range(N, -1, -1):
        if j == 0:
            s = s_
        else:
            s = s_[:-j]

        tmp_ans += [s.count('AC')]
    ans += [tmp_ans]

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

Submission status: Time Limit Exceeded

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

#tmp_list = np.zeros(N)
#ans = []
#for i in range(N-1):
#    if S[i] == 'A' and S[i+1] == 'C':
#        ans.append(int(i))

for i in range(Q):
    lr = input().split()
    tmp = S[int(lr[0])-1:int(lr[1])]
    tmp.replace("G", "").replace("T", "")
    count = tmp.count('AC')
    print(str(count))

Submission status: Time Limit Exceeded

Solution code:
_,q= list(map(int, input().split()))
S=list(input())
 
for i in range(q):
  a,b=list(map(int, input().split()))
  counter=0
 
  for j in range(b-a):
    if S[a-1+j] == "A":
      if S[a+j] == "C":
        counter +=1
 
  print(counter)

Submission status: Time Limit Exceeded

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

place_of_AC = []
for i in range(len(s) - 1):
  if s[i:i+2] == "AC":
    place_of_AC.append(1)
  else:
    place_of_AC.append(0)
    
for _ in range(q):
  l, r = map(int, input().split(" "))
  out = sum(place_of_AC[l-1:r-1])
  print(out)

Submission status: Time Limit Exceeded

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

S = input()
ans = []

for i in range(len(S)):
    if S[i:i + 2] == 'AC':
        ans.append(i)


for i in range(Q):
    l, r = map(int, input().strip().split())
    ret = 0
    ali, ari = 0, 0

    for a in ans:
        if a == r-1:
            ret -= 1
        if l - 1 <= a and a < r:
           ret += 1
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import re

N, S = map(int, input().split(' '))
pattern = "AC+"
T = input()
for _ in range(S):
    first,final = map(int, input().split(' '))
    result = re.findall(pattern, T[first -1:final])
    print(len(result))

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, 2):
        if 'A' == S[j+l-1]:
            if 'C' == S[j+l]:
                count += 1
        elif 'C' == S[j+l-1]:
            if j == 0:
                continue
            if 'A' == S[j+l-2]:
                count += 1
    print(count)

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:
N,Q=map(int, input().split())
S=list(input())
A = []
for i in range(Q):
  A.append(list(map(int, input().split())))
for i in range(Q):
  print(("".join(S[A[i][0]-1:A[i][1]])).count("AC"))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S=input()
a = []
for i in range(Q):
    a.append(list(map(int, input().split())))
#another
L=len(S)
before_moji='0'
keep_start_index=[]
for index in range(L):
    moji=S[index]
    if (before_moji=='A') and (moji=='C'):
        keep_start_index.append(index)
    before_moji=moji

for i in range(Q):
    if a[i][1]-a[i][0]==0:
        print(0)
    else:
        hani = list(range(a[i][0],a[i][1]))
        #print(hani)
        l1_l2_and = set(keep_start_index) & set(hani)
        print(len(l1_l2_and))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

N,Q = inr()
S = inn()
for q in range(Q):
    l,r = inr()
    bubun = S[l-1:r]

    cou = 0
    ccc = 0
    for b in bubun:
        if b == "C":
            if ccc ==1:
                cou += 1
            ccc = 0
        elif b == "A":
            ccc = 1
        else:
            ccc = 0

    print(cou)

Submission status: Time Limit Exceeded

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

for i in range(q):
    count = 0
    s_new = s[lr[i][0]-1:lr[i][1]]
    count = s_new.count("AC")
    print(count)

Submission status: Time Limit Exceeded

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

#print(N,Q)
#print(S)
#print(l)

ans = []
for i in range(Q):
    #print(l[i][1])
    #print(S[l[i][0] - 1], S[l[i][1] - 1])
    #print(S[l[i][0]-1 : l[i][1]])
    R = S[l[i][0]-1 : l[i][1]]
    #print(R)
    ans.append(R.count("AC"))
#print(ans)
for A in ans:
    print(A)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a_loc = set()
for i in range(len(S)):
    if S[i:i+2] == 'AC':
        a_loc.add(i)
ans = [0]*Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    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: Time Limit Exceeded

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

n,q=map(int,input().split())
s=input()
lr=[input() for __ in range(q)]

ans=[]

for i in lr:
    l,r=map(int,i.split())
    #print(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2))
    #ans.append(str(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2)))
    st=s[l-1:r]
    ans.append(str(int((len(st)-len(st.replace('AC',"")))/2)))

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

Submission status: Time Limit Exceeded

Solution code:
import re
# パターンにマッチしたすべてをリストとして返す
N,Q =map(int,input().split())
S = input()
List=[[int(j) for j in input().split()] for i in range(1,Q+1)]
for i in range(Q):
    matchedList = re.findall(r"AC",S[List[i][0]-1:List[i][1]])
    print(len(matchedList))

Submission status: Time Limit Exceeded

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

ac = [0]*n


for i in range(1,n):
	if s[i] =='C':
		if s[i-1] == 'A':
			ac[i-1] = 1

for i in range(q):
	l,r = map(int, lr[i].split())
	answer = sum(ac[l-1:r])
	if answer >= 1:
		if ac[r-1] == 1:
			answer -= 1
	print(answer)

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)]
ans = []

for l, r in l_r_list:
    S_lr = S[l - 1:r]
    ans.append(str(S_lr.count("AC")))

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

Submission status: Time Limit Exceeded

Solution code:

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

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

    counter = 0

    while l < r :
        
        if S[l] == "C":
            if S[l-1] == "A":
                counter+=1

        l+=1

    print(counter)

    Q -= 1

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)]

def c(num):
    return len(re.findall('AC', S[:num]))

for m in l:
    print(c(m[1])-c(m[0]))

Submission status: Time Limit Exceeded

Solution code:
#n=int(input())
#li=input().split()
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
import math

lis=[]
#N Q
li=list(map(int,input().split()))
S=input()
for i in range(li[1]):
    #l_i r_i
    lr=list(map(int,input().split()))
    lis.append(lr)
L=[0]*li[0]
for i in range(li[0]-1):
    if S[i:i+2]=="AC":
        L[i]+=1
for i in range(li[1]):
    ans=0
    ans=sum(L[lis[i][0]-1:lis[i][1]-1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())

A  =input()

for i in range(b):
    x, y = map(int, input().split())
    B = A[x-1:y]
    print(B.count('AC'))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
array = []
for i in range(n-1):
    if (s[i] == "A" and s[i+1] == "C"):
        array.append(i)

for i in range(q):
    a, b = map(int, input().split())
    ans = 0
    for m in array:
        if (a-1 <= m < b-1):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
nq = list(map(int, input().split()))
n = nq[0]
q = nq[1]
s = input()
ac = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ac.append(i)
for i in range(q):
    lr = list(map(int, input().split()))
    l = lr[0]
    r = lr[1]
    ans = 0
    for j in ac:
        if l - 1 <= j < r - 1:
            ans += 1
        elif j >= r - 1:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
S = input()
ans = 0
for _ in range(Q) :
    l, r = map(int,input().split())
    new_S = S[l-1:r]
    for i in range(len(new_S)) :
        if new_S[i:i+1] == "A" :
            if new_S[i+1:i+2] == "C" :
                ans += 1
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
s = input()
ls = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
  print(s[int(ls[i][0]) - 1:int(ls[i][1])].count('AC'))

Submission status: Time Limit Exceeded

Solution code:

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

a = [0]*Q

for i in range(Q):
    l,r = map(int,input().split())
#    partS = S[l-1:r]
#    for j in range(r-l):
#        if S[l-1+j] == 'A' and S[l+j] == 'C':
#            a[i] += 1
    findAC = True
    n = 0
    while(findAC):
        n = S.find("AC",l-1,r)
        if n == -1:
            findAC = False
        else :
            a[i] += 1
            l = n + 2

#    a[i] = partS.count("AC") 

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

Submission status: Time Limit Exceeded

Solution code:
""" AtCoder """

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

l = []
pos = 0

for _ in range(S.count("AC")):
    i = S.index("AC")
    l.append(i + pos + 1)
    pos = pos + i + 2
    S = S[i + 2:]

check = True

for i in range(Q):
    while True:
        if lr[i][0] not in l:
            lr[i][0] += 1
        else:
            break
        if lr[i][0] > lr[i][1]:
            check = False
            break
    while True:
        if (lr[i][1] - 1) not in l:
            lr[i][1] -= 1
        else:
            break
        if lr[i][1] < lr[i][0]:
            check = False
            break
    if check:
        print(l.index(lr[i][1] - 1) - l.index(lr[i][0]) + 1)
    else:
        print(0)
    check = True

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import re

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

S = input()
m = [0] * len(S)
cnt = 0

for idx in [n.span()[0] for n in re.finditer("C", S)]:
    if S[idx-1] == "A":
        cnt += 1
        m[idx] = cnt

for i in range(Q):
    s, e = map(int, input().split())
    cnt_s = max(m[:s])
    cnt_e = max(m[s-1:e])
    print(cnt_e - cnt_s)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

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

S = input()

AC = {}
for i in range(len(S) - 1):
    if S[i] == 'A':
        if S[i + 1] == 'C':
            AC[i] = True
            continue
    AC[i] = False

ans = []

for i in range(Q):
    li, ri = map(int, input().split())
    count = 0
    for i in range(li - 1, ri - 1):
        if AC[i]:
            count += 1
    ans.append(count)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# 入力
n, q = map(int, input().split())
s = list(input())
data = []
for i in range(q):
    l, r = map(int, input().split())
    data.append([l, r])
# 処理
a_data = []
for i in range(q):
    cnt = 0
    ss = s.copy()
    del ss[:data[i][0]-1]
    del ss[data[i][1]-1:]
    a_data = [k for k, x in enumerate(ss) if x == 'A']
    for j in range(len(a_data)):
        try:
            if ss[a_data[j] + 1] == 'C':
                cnt += 1
        except IndexError:
            pass
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = input()
#t = []
lens =len(s)


def f(x):
    if s[x] == "A" and s[x+1] == "C":
        return 1
    else:
        return 0

t = [f(i) for i in range(lens-1)]

#for i in range(len(s)-1):
#    if s[i] == "A" and s[i+1] == "C":
#        t.append(1)
#    else:
#        t.append(0)

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

Submission status: Time Limit Exceeded

Solution code:
#GeT AC

n, q= map(lambda x: int(x), input().split(' '))
s= input()
for i in range(q):
    l, r= map(lambda x: int(x), input().split(' '))
    internal_s= s[l-1:r]
    replaced_inteernal_s= internal_s.replace('AC', '')
    gap= int((len(internal_s)-len(replaced_inteernal_s))/2)
    print(gap)

Submission status: Time Limit Exceeded

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

for i in range(q):
    count = 0
    start = lr[i][0]-1
    end = lr[i][1]
    s_new = s[start:end]
    count = s_new.count("AC")
    print(count)

Submission status: Time Limit Exceeded

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


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

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())
    strs = s[l - 1 : r]
    
    print(strs.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
n,q = (int(i) for i in input().split())  
s = input()
for i in range(q):
    cnt = 0
    li,ri = (int(x) for x in input().split())
    length = ri-li
    for p in range(li-1,ri-1):
        # print(p,s[p:p+2])
        if s[p:p+2] == "AC":
            cnt+=1
            p+=2
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n = [int(i) for i in input().split()]
s = input()
t = [0] *(len(s))
for i in range(len(s)-2):
    if s[i:i+2] == "AC":
        t[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 = map(int, input().split())
S = input()
numbers = []
answers = []
for i in range(Q):
    numbers.append(list(map(int, input().split())))
    answers.append(S[numbers[i][0]-1:numbers[i][1]].count('AC'))
for answer in answers:
    print(answer)

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]+S[j+1]=='AC':
    z.append(j+1)
for i in range(Q):
  l,r = map(int,input().split())
  l = l
  r = r
  ans = [x for x in z if x >= l and x<= r-1]
  print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,mondaisuu=map(int,input().split())
s=input()
li=np.zeros(n)
dp = [[-1 for i in range(n)] for j in range(n)]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    li[i]=1
for i in range(mondaisuu):
  l,r=map(int,input().split())
  if dp[l-1][r-1]==-1:
    ans=int(np.sum(li[l-1:r-1]))
    print(ans)
    dp[l-1][r-1]=ans
  else:
    print(dp[l-1][r-1])

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int, input().split()))
S=input()
ac_indexes=[]
for i in range(N-1):
    if S[i]=='A':
        if S[i+1]=='C':
            ac_indexes.append(1)
        else:
            ac_indexes.append(0)
    else:
        ac_indexes.append(0)

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

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:
#!/usr/bin/env python
# coding: utf-8

# In[22]:


N,Q = map(int, input().split())
S = str(input())
#data = []
#for i in range(Q):
#    data.append(list(map(int, input().split())))
data = []
for i in range(Q):
    data= list(map(int, input().split()))
    print(S[data[0]-1:data[1]].count("AC"))


# In[23]:


#for j in range(Q):
#    print(S[data[j][0]-1:data[j][1]].count("AC"))


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
s = input()
sMap = []
tmp = 0
L = []
R = []
for i in range(Q):
    a = list(map(int, input().split()))
    L.append(a[0])
    R.append(a[1])
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)

for r in range(Q):
    tmp = 0
    for b in range(L[r]-1, R[r]-1):
        if sMap[b] == 1:
            tmp += 1
    print(tmp)

Submission status: Time Limit Exceeded

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

ACpos = []
Apos = -1
for i in range(N - 1):
    if("A" == S[i]):
        Apos = i
    if(("C" == S[i]) & (i - 1 == Apos)):
        ACpos.append(Apos + 1)
        Apos = -1
#print("ACpos = {}".format(ACpos))

for idx in lr:
    cnt = 0
    for pos in ACpos:
        if((idx[0] <= pos) & (pos < idx[1])):
            cnt += 1
#    print("cnt = {}, idx = {}".format(cnt, idx))
    print(str(cnt))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[63]:


N,Q=map(int,input().split())
S=input()
lr=[list(map(int,input().split())) for l in range(Q)]
ct=0
for i in range(Q):
    #t=S[lr[i][0]-1:lr[i][1]]
    #t=[S for j in range(lr[i][0],lr[i][1])]
    #print(t)
    for j in range(lr[i][0]-1,lr[i][1]-1):
        if S[j]=='A' and S[j+1]=='C':
            ct+=1
    print(ct)
    ct=0
   # if i==Q:
    #    break


# In[ ]:

Submission status: Time Limit Exceeded

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

for k in range(len(S) - 1):
    if S[k] == 'A':
            if S[k+1] == 'C':
                    cnt.append(1)
            else:
                    cnt.append(0)
    else:
            cnt.append(0)



for lr in lrs:
    sums = 0
    for k in range(lr[0]-1,lr[1]-1):
        sums += cnt[k]
    print(sums)

Submission status: Time Limit Exceeded

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:
        cnt = 0
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        for i in range(R-L):
            #print(i)
            cnt += cntAC(R-i-1, R-i, S)
        print(cnt)
    return
 

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,Q = map(int,input().split())
    S = input()
    lr = []
    for i in range(Q):
        lr.append(list(map(int,input().split())))

    cl = [0 for _ in range(len(S))]

    for i in range(1,len(S)):
        if S[i] == 'C' and S[i-1] == 'A':
            cl[i] = cl[i-1] + 1
        else:
            cl[i] = cl[i-1]


    #print(cl) 
    #print(S)

    for l,r in lr:
        sub = cl[l-1:r]
        res = cl[r-1] - cl[l-1] 
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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