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:


tmp = input().split(" ")
n = tmp[0]
q = int(tmp[1])

s = input()

ac_indexes=[]
start=0
while True:
    ind = s.find("AC", start)
    if ind != -1:
        start=ind+2
        ac_indexes.append(ind)
    else:
        break

for i in range(q):

    if len(ac_indexes) == 0:
        print ("0")
        continue

    tmp = input().split(" ")
    a = int(tmp[0]) - 1
    b = int(tmp[1]) - 2

    left = 0
    right = len(ac_indexes)-1
    left_kari=-1
    left_kakutei = -1
    while left <= right:
        center = (left+right)//2
        if ac_indexes[center] > a:
            right = center-1
            left_kari = center
        elif ac_indexes[center] < a:
            left = center+1
        else:
            left_kakutei = center
            break
    if left_kakutei == -1:
        left_kakutei = left_kari
    
    left = 0
    right = len(ac_indexes)-1
    right_kari = -1
    right_kakutei = -1
    while left <= right:
        center = (left+right)//2
        #print (left, center, right)
        if ac_indexes[center] > b:
            right = center-1
        elif ac_indexes[center] < b:
            left = center+1
            right_kari = center
        else:
            right_kakutei = center
            break
    if (right_kakutei == -1):
        right_kakutei = right_kari

    if (left_kakutei > right_kakutei or left_kakutei==-1 or right_kakutei==-1):
        print ("0")
        continue

    print(str(right_kakutei - left_kakutei + 1))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = list(input())
#S  = input()
s = []
for i in range(Q):
    l,r = map(int,input().split())
    s.append(0)
    for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            s[i] += 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:
num,que = map(int,input().split(" "))
word = input()

for i in range(que):
    s,e = map(int,input().split(" "))
    ex_word = word[s-1:e]
    answer = ex_word.count("AC")
    print(answer)

Submission status: Time Limit Exceeded

Solution code:





N,Q = map(int,input().split())
S = []
for c in str(input()):
    S.append(c)

for i in range(Q):
    l, r = map(int, input().split())
    count = 0
    for i in range(len(S[int(l-1):int(r)])-1):
        if (S[int(l-1):int(r)][i] == "A"):
            if (S[int(l-1):int(r)][i+1] == "C"):
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

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())))
    rice = S[numbers[i][0]-1:numbers[i][1]]
    answers.append(rice.count('AC'))
for answer in answers:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []

for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break

for i in range(Q):
    l, r = (int(i) for i in input().split())
    result = [i for i in onon if i >= l and i <= (r - 1)]
    print(len(result))

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":   
        for j in range(n):
            dp[i][j]=dp[i-1][j]-1
    else:
        for j in range(n):
            dp[i][j]=dp[i-1][j]        
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

Submission status: Time Limit Exceeded

Solution code:
i = input()
n, q = int(i.split()[0]), int(i.split()[1])
s = input()
_list = []
u = 0
while True:
    i = input()
    u += 1
    _list.append((int(i.split()[0]), int(i.split()[1])))
    if u == q:
        break

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:
import numpy as np
n, q = map(int, input().split())
s = input()
ac_list = np.array([0]*len(s))
i = 0
'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1:] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import re
N,Q=[int(e) for e in input().split(' ')]
S=input()
qs=[]
for i in range(Q):
    qs.append([int(e) for e in input().split(' ')])

sts=[]
for i in range(N):
    if i>0:
        if S[i-1:i+1]=='AC':
            sts.append(i)

for q in qs:
    print(len([1 for e in sts if e>=q[0] and e<q[1]]))
#    print(len(re.findall('AC',substr)))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, q = (int(i) for i in input().split())
s = input()
l,r = [],[]
for i in range(q):
    tmp = [int(i) for i in input().split()]
    l.append(tmp[0]-1)
    r.append(tmp[1]-1)
# AC_index = []
# while 'AC' in s:
#     index = s.index('AC')
#     AC_index.append(index + len(AC_index) * 2)
#     if index < (len(s) - 1):
#         s = s[:index] + s[index + 2:]
#     else:
#         s = s[:index]

# for i in range(q):
#     left_index = bisect.bisect_left(AC_index, l[i])
#     right_index = bisect.bisect_right(AC_index, r[i])
#     if AC_index[right_index - 1] == r[i]:
#         right_index -= 1
        
#     print(right_index-left_index)
for i in range(q):
    tmp = s[l[i]:r[i] + 1]
    tmp = tmp.replace('AC', '00')
    print(tmp.count('0')//2)

Submission status: Time Limit Exceeded

Solution code:
#8 3
#ACACTACG
#=> ACACxACx
#3 7
#2 3
#1 8
import time
start = time.time()

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

p_list=[]
cnt=0

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

#print p_list

for i in range(Q):
    q_a, q_b = map(int,raw_input().split())
#    print S[q_pos[0]-1:q_pos[1]]

    cnt = len([p for p in p_list if (p >= (q_a-1)) and (p <(q_b-1))])

 #    cnt = 0
 #    for p in p_list:
 #        if (p >= (q_a-1)) and (p <(q_b-1)):
 # #            print q_pos[0]-1, p, q_pos[1]-1
 #            cnt += 1
    print cnt

#print format(time.time() - start)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
b = input()
a = [[int(x) for x in input().split()] for _ in range(q)]
ans=[0]
for j in range(len(b)-1):
        if b[j] == "A" and b[j+1] == "C":
            ans.append(1)
        else:
            ans.append(0)
for i in a:
    print(sum(ans[i[0]:i[1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
# import bisect
# import math
# import itertools
import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, q = ip.IL()
    s = ip.S()
    # lr = ip.SILS(q)

    li = [i for i in r(n - 2) if s[i] == "A" and s[i + 1] == "C"]

    for _ in r(q):
        x, y = ip.IL()
        x -= 1
        y -= 1
        if (y - x) % 2 != 0:
            y -= 1
        li = np.array(li)
        b = np.where((x <= li) & (li <= y), 1, 0)
        print(sum(b))


main()

Submission status: Time Limit Exceeded

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

flag=0
for num,i in enumerate(S):
    if i=='A':
        flag=1
    elif i=='C' and flag==1:
        count_list.append(num)
        flag=0
    else:
        flag=0

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:
import re
N, Q = map(int,input().split())
S = input()

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  m = re.findall('AC',Si)
  if m != []:
    print(len(m))
  else:print(0)

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())
    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:
a = input().split(" ")
n = int(a[0])
q = int(a[1])
s = input()
ans = [0] * q
for i in range(0, q):
	c = input().split(" ")
	l = int(c[0])
	r = int(c[1])
	ns = s[l-1:r]
	d = [0]
	e = len(ns)
	for j in range(0, e-1):
		if ns[j] == "A":
			if ns[j+1] == "C":
				ans[i] += 1
for i in ans:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N, Q = map(int, input().split())
S = input()
for i in range(Q):
    q1 = list(map(int, input().split()))
    cnt = 0
    qs = S[q1[0]-1: q1[1]]
    print(qs.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):
    c = 0
    word_s = l[i][0] - 1
    word_e = l[i][1]
    for m in re.findall('AC', S[word_s:word_e], re.MULTILINE):
        c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
length = list(map(int,input().split()))	
string = input()
l_r = [list(map(int,input().split())) for i in range(length[1])]
answer = []

for i in range(length[1]):
  part_str = string[(l_r[i][0]-1):l_r[i][1]]
  for n in range(len(part_str)):
    answer.append(0)
    if part_str[n]=='A':
      if n != (len(part_str)-1):
        if part_str[n+1]=='C':
          answer[i] += 1
  print(answer[i])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
S = input().replace("G","").replace("T","")

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(i) for i in input().split())
S = input()
lr = []
for _ in range(Q):
    lr.append([int(i) for i in input().split()])  # S += [input()] とも書けるprint(lr)
# print(lr)
# print(S)
for lis in lr:
    l = lis[0]
    r = lis[1]
    part = S[l - 1:r]
    # print(part)
    part2 = part.replace("AC", "")
    # print("part", part2)
    print(int((len(part) - len(part2)) / 2))

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):
  ac = re.findall("AC", Str)
  l_ac = len(ac)
  return l_ac

for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(func(S[l-1:r]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# coding: utf-8
n = [int(i) for i in input().split()]
s = input()
for i in range(n[1]):
    a = 0
    m = [int(j) for j in input().split()]
    for j in range(m[1]- m[0] ):
        if s[m[0]+j:m[0]+1+j] != "A":
            i += 1
        if s[m[0]-1+j:m[0]+1+j] == "AC":
            #print(s[m[0]-1+j:m[0]+1+j])
            #print(j)
            a += 1
            i += 1

            
    print(str(a))

Submission status: Time Limit Exceeded

Solution code:
hajime = input().split(" ")
num = int(hajime[1])
word = input()
syori = []
for i in range(num):
  syori.append(input())

for i in syori:
  wakeru = i.split(" ")
  a = int(wakeru[0])
  b = int(wakeru[1])
  tmp = word[a-1:b]
  print(tmp.count("AC"))

Submission status: Time Limit Exceeded

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

for i,x in l:
    s1 = S[i-1:x]
    print(s1.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 not in dp:
        dp[l+r] = len(t.split('AC'))-1
    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())
string = input()
a = []
for i in range(Q):
    ans = 0
    count = 0
    l,r = map(int,input().split())
    sp_str = string[l-1:r]
    print(sp_str.count('AC'))

Submission status: Time Limit Exceeded

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

for j in lr:
  i = s[j[0]-1:j[1]]
  print(i.count('AC'))

Submission status: Time Limit Exceeded

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

s = list(input())

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

s.append("P")

def at(start, last):
    ans = 0
    for i in range(start-1,last-1):
        if s[i] == "A":
            if s[i+1] == "C":
                ans += 1
    return ans

for i in range(q):
    print(at(l[i][0],l[i][1]))

Submission status: Time Limit Exceeded

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

A = [0 for i in range(n)]

for i in range(n):
    if i == n-1:
        break
    if s[i] == "A":
        if s[i+1] == "C":
            A[i] = 1

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

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

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

lst=[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        lst.append(i)

ans=[]
for j in range(Q):
    count=0
    l,r = lr[j][0]-1, lr[j][1]-1
    for p in lst:
        if l <= p and p+1 <= r:
            count += 1
    ans.append(count)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def main():
  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)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

    num_acs = []
    for i in range(q):
        li, ri = inputAsIntArr()

        num_ac = 0
        for j in range(li-1, ri-1):
            if s[j] != 'A':
                continue
            if s[j+1] == 'C':
                num_ac += 1
                j += 1
        num_acs += [str(num_ac)]

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


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


if __name__ == '__main__':
    main()

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]
    print(bubun.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
import re
import numpy as np

N, Q  = [int(i) for i in input().split()]

S = input()

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

m = re.finditer('AC', S)

B = []
C = []

for match in m:
    B.append(match.start())
    C.append(match.end())

B = np.array(B)
C = np.array(C)
#print(B)
    
#print(C)
for x in A:
    D = B >= x[0]-1
    E = C <= x[1]
    print(np.sum(D &E ))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

for line in sys.stdin:
  l,r = list(map(int, line.strip().split(' ')))
  c = 0
  for i in idx:
    if l <= i <= r-1:
      c += 1
    else:
      continue
  print(c)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    str = S[lr_lists[i][0] -1:lr_lists[i][1] ]
    print(str.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
def main():
    line = input()
    line = line.split(' ')
    n = int(line[0])
    q = int(line[1])
    s = input()
    for i in range(0,q):
        line = input() 
        line = line.split(' ')
        print(find_ac(s[int(line[0])-1:int(line[1])]))

def find_ac(s):
    cnt = 0
    for s1, s2 in zip(s[0::2],s[1::2]):
        if s1 == 'A' and s2 == 'C':
            cnt += 1
    
    for s1, s2 in zip(s[1::2],s[2::2]):
        if s1 == 'A' and s2 == 'C':
            cnt += 1

    return cnt

main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
#s=list(input())	
s = input()
index = -1
indexes = []
while True:
    index = s.find("AC", index + 1)
    if index == -1:
        break
    indexes.append(index)

for i in range(q):
    l,r = map(int,input().split())
    ans1 = -1
    ans2 = len(indexes) - 1
    for j in range(len(indexes)):
        if(l -1 <= indexes[j] and ans1 == -1):
            ans1 = j
        if (r < indexes[j]+2):
            ans2 = j -1
            break
    if (ans1 == -1):
        ans2 = -2
    print(ans2-ans1 + 1)

Submission status: Time Limit Exceeded

Solution code:
NQ = list(map(int, input().split()))
word = input()
word_list = []
for i in word:
    word_list.append(i)
for i in range(0, NQ[1]):
    rl = list(map(int, input().split()))
    word = word_list[rl[0]-1:rl[1]]
    word = ''.join(word)
    print(word.count('AC'))

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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


for i in range(N[1]):
	work=S[l[i][0]-1:l[i][1]]
	a=len(work)
	work=work.replace("AC","")
	print((a-len(work))//2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    s_q = s[l-1:r]
    retSum = 0
    for j in range(len(acpos)):
        if l <= acpos[j] and r > acpos[j]:
            retSum +=1
        if r <= acpos[j]:
            break
    print(retSum)

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):
    l,r = lr_list[i][0]-1, lr_list[i][1]-1
    ans = sum(ac_tf_list[l:r])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 2
    bl = bisect.bisect_left(index, l)
    br = bisect.bisect_left(index, r)
    if r in set(index):
        print(br - bl + 1)
    else:
        print(br - bl)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n = [int(i) for i in input().split()]
s = input()
for i in range(n[1]):
    a = 0
    m = [int(j) for j in input().split()]
    for j in range(m[1]- m[0] ):
        if s[m[0]-1+j:m[0]+1+j] == "AC":
            #print(s[m[0]-1+j:m[0]+1+j])
            #print(j)
            a += 1
            i += 1
        if s[m[0]+j:m[0]+1+j] != "A":
            i += 1
            
    print(str(a))

Submission status: Time Limit Exceeded

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

def f(i):
    cnt = 0
    for j in range(i-1):
        #print(s[j:j+2])
        if s[j:j+2] == 'AC':
            cnt += 1
    return cnt

for _ in range(q):
    l, r = list(map(int, input().split()))
    #print(s[l-1:r])
    print(f(r) - f(l))

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

Submission status: Time Limit Exceeded

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

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

ei = []
for index, item in enumerate(s):
    if index == n - 1:
        break
    if s[index] == "A" and s[index + 1] == "C":
        ei.append(index)

for i in range(0,q):
    sum = 0
    for j in range(int(lr[i][0])-1,int(lr[i][1])):
        if j in ei:
            sum += 1
    if int(lr[i][1])-1 in ei:
        sum -= 1
    print(sum)

Submission status: Time Limit Exceeded

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

    ans = []
    ac = 'AC'
    for q in range(Q):
        lq, rq = input().split()
        S_sub = S[int(lq) -1 : int(rq)]
        ans.append(S_sub.count(ac))

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


if __name__ == '__main__':
    C()

Submission status: Time Limit Exceeded

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

import sys

def parse_input(lines_as_string = None):

    lines = []
    if lines_as_string is None:
        lines.append(input())
        tokens = lines[0].split(" ")
        n = int(tokens[0])
        q = int(tokens[1])
        lines.append(input())
        for i in range(q):
            lines.append(input())
    else:
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        print("lines=%s" % lines)
        tokens = lines[0].split(" ")
        n = int(tokens[0])
        q = int(tokens[1])

    s = lines[1]

    l = []
    r = []
    for i in range(q):
        tokens = lines[i+2].split(" ")
        l.append(int(tokens[0]))
        r.append(int(tokens[1]))

    return (n, q, s, l, r)

def solve(n, q, s, l, r):

#    result = []
    for i in range(q):
        b = l[i] - 1
        e = r[i] - 1
        count = 0
        ss = s[b:e+1]
        len_ss = len(ss)
        j = 0
        while j < len_ss:
#            print("ss=%s" % ss)
            if ss[j] == "A" and j + 1 < len_ss and ss[j+1] == "C":
                count = count + 1
                j = j + 2
            else:
                j = j + 1
        print(count)
#        result.append(count)
    
#    return result

def main():
    solve(*parse_input())
#    print("%d" % solve(*parse_input()))

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

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

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]
    SSL = [SS[n:n+2] for n in range(len(SS) - 1) if SS[n:n+2] == 'AC']
    print(len(SSL))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 2
    bl = bisect.bisect_left(index, l)
    br = bisect.bisect_left(index, r)
    if r in index:
        print(br - bl + 1)
    else:
        print(br - bl)

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