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:
i = input()
n, q = int(i.split()[0]), int(i.split()[1])
s = input()
_list = []

for x in range(0, q):
    i = input()
    _list.append((int(i.split()[0]), int(i.split()[1])))

for x in _list:
    _str = s[x[0]-1:x[1]]
    n = 0
    for y in range(2, len(_str) + 1):
        if _str[y-2:y] == "AC":
            n += 1
    print(n)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = str(input())
k = [ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)]
#print(k)
for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    #print(k[a:b+1])
    ans = sum(k[a:b+1])
    if k[a] == 1:
        ans -= 1
    print(ans)

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!=i:
            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":   
        t=-1
    for j in range(n):
        dp[i][j]=max(dp[i-1][j]+t,0)
        
        
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()
S = S.translate(str.maketrans({"T":"0","G":"0"}))
for q in range(Q):
  l, r = map(int, input().split())
  si = S[l-1:r].replace("AC","11")
  si = si.translate(str.maketrans({"A":"0","C":"0"}))
  print(int(sum(map(int,list(si)))/2))

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

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-1)
    before_moji=moji
for i in range(Q):
    answer=0
    if a[i][1]-a[i][0]==0:
        pass
    else:
        for start in keep_start_index:
            if a[i][0]<=start+1<a[i][1]:
                answer+=1
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import re
pattern = 'AC'
n, q = map(int, raw_input().split())
s = raw_input()

x = [raw_input() for i in range(q)]

result = re.finditer(pattern, s)

ac = np.zeros(len(s))
for match in result:
    ac[match.span()[0]] = 1

#print ac



for d in x:
    r = d.split(' ')
    start = int(r[0])-1
    end = int(r[1])
    wa = sum(ac[start:end])
    if ac[end-1]==1: wa = wa-1
    print int(wa)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,mondaisuu=map(int,input().split())
s=input()
li=np.zeros(n)
dp = [[0 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]==0:
    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 = input().split()
n = int(n)
q = int(q)
s = input()
ls = [input().split() for _ in range(q)]

for i in range(q):
  cnt = 0
  for h in range(int(ls[i][1]) - int(ls[i][0])):
    if s[h - 1] == 'A' and s[h] == 'C':
      cnt += 1
    else:
      pass
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N, M = (int(i) for i in input().split())
moji = input()
e = [[int(i) for i in input().split()] for i in range(M)]

c_list = []

for idx in e:
    sub = moji[idx[0]-1:idx[1]]
    if 'AC' in sub:
        print(sub.count('AC'))
    else:
        print(0)

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
 



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

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

Submission status: Time Limit Exceeded

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

for i in range(q):
    info.append(list(map(int,input().split())))
    print(s[info[i][0]-1:info[i][1]].count("AC"))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import re

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

# ゴリ押し実装
sj = '92'.join(S.split('AC'))
sj = re.sub('[A-Z]', '0', sj)
sj = [-1 if s == '9' else int(s) for s in list(sj)]

for i in range(Q):
  l, r = map(int, input().split())
  ret = sj[(l-1):r]
  if ret[0] == 2:
    ret[0] = 0
  if ret[-1] == -1:
    ret[-1] = 0
  print(sum(ret))

Submission status: Time Limit Exceeded

Solution code:
import re
N, Q = map(int, input().split())
S = input()
iter = re.finditer("AC", S)
indices_C = [m.start(0)+1 for m in iter]
total = S.count("AC")

dec_l_list = []
dec_l = 0
dec_r_list = []
dec_r = total
for i in range(N):
    if i in indices_C:
        dec_l += 1
        dec_r -= 1
    dec_l_list.append(dec_l)
    dec_r_list.append(dec_r)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N, Q = map(int, input().split())
S = input()

#ACの位置を探す
list = []
n = -2
while n != -1 : 
    n = S.find("AC", n+2)
    list.append(n)

list.pop(-1)
#print(list)
    

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

    print(count)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
  N, Q = map(int, input().split())
  l = input()
  for i in range(Q):
    sublist = []
    left, right = map(int, input().split())
    sublist = l[left-1:right]
    print(sublist.count('AC'))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = input()
n=0
m=0
for i in range(M):
    n,m=list(map(int, input().split()))
    print(S[n-1:m].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
def solve(N, Q, S, L_R):
    answers = [None] * Q
    ac_index = list()
    for i in range(len(S) - 1):
        s = S[i:i + 2]
        if s == "AC":
            ac_index.append(i)
    q = 0
    for l, r in L_R:
        ans = 0
        for ac in ac_index:
            if l - 1 <= ac < r - 1:
                ans += 1
        answers[q] = ans
        q += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

Submission status: Time Limit Exceeded

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)

ans = [0]*Q
for i in range(Q):
    l, r = list(map(int, input().split()))
    cnt = 0
    for j in idx:
        if l <= j < r:
            cnt += 1
    ans[i] = cnt

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(Q):
    Stmp = S[lr[i][0]-1: lr[i][1]]
    tmp = 0
    ans = 0
    while tmp != len(Stmp) -1:
        if Stmp[tmp] =="A" and Stmp[tmp+1]=="C":
            ans += 1
        tmp += 1
    print(ans)

Submission status: Time Limit Exceeded

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

arr = [[0 for j in range(N)] for i in range(N)]
A_tmp = 0

for i in range(N):
    if S[i] == "A":
        A_tmp = 1
    elif A_tmp == 1 and S[i] == "C":
        for j in range(i, N):
            arr[i-1][j] = 1
        A_tmp = 0
    else:
        A_tmp = 0

for i in range(N-1,-1,-1):
    for j in range(len(S)):
        if i < j:
            arr[i][j] = arr[i+1][j] + arr[i][j]







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

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

Submission status: Time Limit Exceeded

Solution code:
N, Q =  map(int, (input().split(' ')))
S = str(input())
lr = [tuple(map(int, input().split(' '))) for _ in range(Q)]
save = ''
i = 0
#while i < len(S):
#    if S[i] == "A":
#        if S[i+1] == "C":
#            save += 't'
#        else:
#            save += 'f'
#        i += 1
#    elif S[i] == "C":
#        i += 1
#        save += 'f'
#    else:
#        save += 'f'
#        i += 1

for left, right in lr:
    print(S[left-1: right].count('AC'))
    #save[left-1: right-1].count('t')
    #save[left-1: right-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
import collections


def r(n, q, s, l):
    sc = s[l[0]-1:l[1]]
    return sc.count('AC')


def main():
    input = sys.stdin.readline
    n, q = list(map(int, input().split()))
    s = str(input()).strip()
    ql = [tuple(map(int, input().split())) for _ in range(q)]

    for l in ql:
        print(r(n, q, s, l))


if __name__ == '__main__':
    main()

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

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    cnt = 0
    for j in range(len(si)-1):
        if si[j] == "A":
            if si[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=input()
for _ in range(Q):
    ans = 0
    tmp_s=''
    start=0
    end=0
    start,end=map(int,input().split())
    tmp_s = S[start-1:end]
    while "AC" in tmp_s:
        ans += 1
        tmp_s = tmp_s.replace("AC","",1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

_ = input()
S = input().strip()
flag = [1 if S[i:i+2] == 'AC' else 0 for i in range(len(S)-1)]

for line in sys.stdin:
  l,r = list(map(int, line.strip().split(' ')))
  print(sum(flag[l-1:r-1]))

Submission status: Time Limit Exceeded

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

for l,r in list:
    cnt = 0
    S_rep = S[l-1:r].replace('AC','')
    print(int((len(S[l-1:r])-len(S_rep))/2))

Submission status: Time Limit Exceeded

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

count=0
flag=0
idxList=[]
for i in range(len(S)-1):
    if S[i:i+2]=='AC':
        idxList=idxList+[i+1]


for i in range(Q):
    l,r=map(int,input().split())
    print(str(sum(x>=l and x<r for x in idxList)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,Q = map(int,input().split())
S = input()
p = set()
for n,i in enumerate(S[:-1]):
    if i == "A" and S[n+1]=="C":
        p.add(n)
#print(p)
for i in range(Q):
    a,b = map(int,input().split())
    tmp = {}
    tmp = {i for i in range(a-1,b-1)}
#    print(tmp)
    print(len(tmp&p))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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.append(out + len(check_point) * 2)
  
# 指定した文字列範囲を含む要素数を表示
for i in range(Q):
  start, end  = map(int,input().split())
  list_match = [i for i in check_point if (start - 1 <= i) and (i + 1 < end)]
  out = len(list_match)
  print(out)

Submission status: Time Limit Exceeded

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

counter = [0 for _ in range(Q)]
index = -1
while True:
	index = S.find("AC", index+1)

	if index == -1:
		break
	
	for i, (l, r ) in enumerate(data):
		if l-1 <= index < r-1:
			counter[i] += 1


for res in counter:
	print(res)



# print(indexList)

# for (l, r) in data:
	# print(indexList[l-1: r-1])
	# print(sum(indexList[l-1: r-1]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
Q_LIST = []
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()
l = len(s)
S = list()
for i in range(l-1):
    if s[i:i+2:] == 'AC':
        S.append(i+1)
for i in range(q):
    l,r = map(int,input().split())
    cnt = 0
    for j in range(len(S)):
        if l<= S[j] <= r-1:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

l_list = []
r_list = []

s_count = [0]
for i in range(len(S) - 1):
    if S[i:i+2] == 'AC':
        s_count.append(1)
    else:
        s_count.append(0)
     

for x in range(Q):
    l, r = map(int, input().split())
    sub_count = s_count[l:r]
    print(sum(sub_count))

Submission status: Time Limit Exceeded

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

is_ac = [0] * n
for i in range(n-2):
  if s[i] == "A":
    if s[i+1] == "C":
      is_ac[i] = 1
   
for item in lr:
  ans = sum(is_ac[item[0]-1: item[1]])
  if s[item[1]-1] == "A":
    if item[1] != n:
      if s[item[1]] == "C":
        ans -= 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = input()
l = [0] * Q
r = [0] * Q
a = []
for i in range(Q):
    l[i],r[i] = map(int,input().split())

for i in range(N-1):
    
    if S[i] == 'A' and S[i+1] == 'C':

        a.append(1)

    else:

        a.append(0)

for i in range(Q):

    print(a[l[i]-1:r[i]-1].count(1))

Submission status: Time Limit Exceeded

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

for i in range(q):
    l,r=map(int,input().split())
    ss=s[l-1:r]
    m=0
    for j in range(r-l):
            if ss[j]=="A" and ss[j+1]=="C":
                m+=1
    print(m)

Submission status: Time Limit Exceeded

Solution code:

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

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

    s = list(S[int(r)-1:int(l)])
    counter = 0
    oldsp =''
    while len(s) > 0:
        sp = s.pop(0)
        if sp == "C":
            if oldsp == "A":
                counter+=1
        
        oldsp=sp

    print(counter)
    

    Q -= 1

Submission status: Time Limit Exceeded

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

for lr in lr_list:
    l,r = map(int, lr.split())
    count = 0
    aflag = False
    for i in slist:
        if i + 1 >= l and i < r:
            if s[i] == 'A':
                aflag = True
            elif s[i] == 'C' and aflag == True:
                count += 1
                aflag = False
            else:
                aflag = False
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def ac(S):
    L = list(S)
    m = [0] * len(S)
    cnt = 0
    for idx, l in enumerate(L):
        if l == "A":
            m[idx] = 1
        if l == "C":
            if idx != 0 and m[idx-1] == 1:
                cnt += 1
    return cnt

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

for i in range(Q):
    s, e = map(int, input().split())
    print(ac(S[s-1:e]))

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(r - l):
        if 'AC' == S[j+l-1:j+l+1]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
s = input()
#cnt = 0
for i in range(q):
  l, r = map(int,input().split())
  #print(s[l-1:r])
  if 'AC' not in s[l-1:r]:
    print(0)
  else:
    print(s[l-1:r].count('AC'))

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 = {}
 
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]))
        cnt = cntAC(l, r, S[l-1:r])
        print(cnt)
    return
 
 
def cntAC(l, r, t):
    if l+r is not dp:
        dp[l+r] = len(re.findall(r'AC', t))
    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:
N,Q = map(int,input().split())
S = input()
flag = 0
max = S.count('AC')
if max == 0:
    flag = 1
for i in range(Q):
    if flag == 1:
        print(0)
    else:
        L,R = map(int,input().split())
        if L - R + 1 == N:
            print(max)
        else:
            print(S[L-1:R].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
string = input()
a = []
for i in range(Q):
    ans = 0
    count = 0
    l,r = map(int,input().split())
    sp_str = string[l-1:r]
    a.append(sp_str.count('AC'))
for k in a:
    print(k)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

flags = [0] * len_S
AC = ('A', 'C')
for i, v in enumerate(zip(S[:-1], S[1:])):
  flags[i + 1] = 1 if v == AC else 0

sums = list(np.cumsum(flags))

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

Submission status: Time Limit Exceeded

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

for i,x in l:
    s1 = S[i-1:x]
    print(s1.count('AC'))

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)
for j in range(Q):
    count = 0
    for i in range(l[j],r[j]):
        if(S[i]=="A")&(S[i+1]=="C"):
            count = count + 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = input()
a = []
for i in range(M):
    a.append(list(map(int, input().split())))
    print(S[a[i][0]-1:a[i][1]].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
N,Q=[int(x) for x in input().split()]
S=list(input())
Check_list=['A','T','G','C']

for i in range(Q):
  l,r=[int(x) for x in input().split()]
  S_temp=S[l-1:r]
  
  ac_num=0
  
  for l in range(len(S_temp)-1):
    if (S_temp[l]=='A') & (S_temp[l+1]=='C'):
      ac_num+=1
    
  print(ac_num)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    start = lr_lists[i][0] -1
    end = lr_lists[i][1] 
    str = S[start:end]
    

    count = 0
    """
    for j in range(0,len(str)-1):
        if str[j] == "A" and str[j+1] == "C":
            count += 1
    """
    count = str.count("AC")

    print(count)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    l, r = map(int, input().split())
    text = ""
    ans = 0
    
    for j in range(l-1, r-1):
        moji = S[j]
        if moji == "A" or moji == "C" or moji == "G" or moji == "T":
            text += moji
            for k in range(j+1, r):
                if S[k] == "A" or S[k] == "C" or S[k] == "G" or S[k] == "T":
                    text += S[k]
                    if text == "AC":
                        ans += 1
                    #print(i, text)
                else:
                    if text == "AC":
                        print("ac")
                        ans += 1
                    text = ""
                    break
            text = ""
        else:
            text = ""
    print(ans)

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())
answer=[0]*Q
for j in range(Q):
  x=l[j]
  counter=[]
  leng=r[j]-l[j]+1
  counter=[1 if (i!=leng-1)and(S[x-1+i]=="A")and(S[x+i]=="C") else 0 for i in range(leng)]
  answer[j]=sum(counter)
for i in range(Q):
  print(answer[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
L = [list(map(int,input().split())) for i in range(Q)]
P=[]
for k, j in enumerate(S[:-1]):
        if j=="A" and S[k+1]=="C":
            P.extend([1])
        else:
            P.extend([0])
for i in L:
    print(sum(P[i[0]-1:i[1]-1]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
for q in range(Q):
  l, r = map(int, input().split())
  si = S[l-1:r].replace("AC","11")
  si = si.translate(str.maketrans({"A":"0","T":"0","G":"0","C":"0"}))
  print(int(sum(map(int,list(si)))/2))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = input()
li = []
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()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

[print(S[max(0, l[ind]-1) : min(r[ind], N)].count("AC")) for ind in range(Q)]

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

for l,r in lr:
    substr = S[l-1:r]
    res = 0
    for i in range(len(substr)-1):
        if substr[i] == 'A' and substr[i+1] == 'C':
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import re
pattern = r"AC"
N, Q = map(int, input().split(" "))
T = input()

for i in range(Q):
    start, end = map(int, input().split(" "))
    print(len(re.findall(pattern, T[start-1:end])))

Submission status: Time Limit Exceeded

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

for l,r in lr_list:
    tmp_str = ''.join(s[l-1:r])
    print(tmp_str.count('AC'))

Submission status: Time Limit Exceeded

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

hit = [False] * N

for i in range(0, N):
    if S[i:i+2] == 'AC':
        hit[i] = True

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

Submission status: Time Limit Exceeded

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

L=[]
for i in range(Q):
	L.append(map(int, input().split()))

for i in L:
	i=list(i)
	#print(S[i[0]-1:i[1]])
	print(S[i[0]-1:i[1]].count("AC"))

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

for idx in lr:
    sub = S[idx[0] - 1:idx[1]]
    cnt = sub.count("AC")
#    print("cnt = {}, sub = {}".format(cnt, sub))
    print(str(cnt))

Submission status: Time Limit Exceeded

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

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

for lrs in lr:
        print(sum(cnt[lrs[0]-1:lrs[1]-1]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
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:
import re

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

for i in range(Q) :
    subStr = S[L[i][0] - 1:L[i][1]]
    print(subStr.count('AC'))

Submission status: Time Limit Exceeded

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

for q in Q_LIST:
    print(S[q[0] - 1:q[1]].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
s=list(input())
l=[]
def times(l,s):
    first=l[0]-1
    last=l[1]
    ss=[]
    count=0
    #5,4
    for i in range(first,last):
        ss.append(s[i])
    #print(ss)
    for i in range(len(ss)-1):
        if ss[i]=='A':
            if ss[i+1]=='C':
                count+=1
        #print(ss)
    return count

for i in range(Q):
    a=list(map(int,input().split()))
    l.append(a)
#print(l)

    
for c in l:
    ans=times(c,s)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
l=[]; r=[]
for _ in range(Q):
    l1, r1 = map(int, input().split())
    l.append(l1); r.append(r1)
for i in range(Q):
    s = S[l[i]-1:r[i]]
    print(int((r[i]-l[i]+1-len(s.replace("AC","")))/2))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
S = input()
for i in range(q):
    count = 0
    x,y = map(int,input().split())
    S_a = S[x-1:y]
    for j in range(y-x):
        if(S_a[j]=="A"):
            if(S_a[j+1]=="C"):
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S) + 1)]
    c = 0
    for i in range(1, len(S)):
        if S[i - 1:i + 1] == 'AC':
            c += 1
            SL[i + 1:] = [c for _ in range(len(S) - i)]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r] - SL[l])
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
C = input()
for i in range(1,B+1):
  A, B= map(int, input().split())
  slice = C[A-1:B]
  print(slice.count("AC"))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

place_of_AC = []
ind = 0

while True:
  ind = s.find("AC", ind)
  # print(ind)
  if ind != -1:
    place_of_AC.append(ind + 1)
    ind += 2
  else:
    break
#print(place_of_AC)
    
for _ in range(q):
  l, r = map(int, input().split(" "))
  out = [x for x in place_of_AC if l <= x < r ]
  print(len(out))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = str(input())
for i in range(Q):
    l, r = map(int, input().split())
    slice = S[l-1:r]
    qw=len(slice)
    po=slice.replace("AC","")
    le=len(po)
    print(int((qw-le)/2))

Submission status: Time Limit Exceeded

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

for i in range(int(Q)):
  l,r = input().split()
  count = 0
  for x in p:
    if x > int(r)-2:
      break
    
    if int(l)-1 <= x and x <= int(r)-2:
      count += 1
  print(count)