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())
lr = [list(map(int,input().split())) for i in range(q)]
ans = []

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

for i in range(n):
    ans.append(s[:i].count("*"))

for i in lr:
    l = i[0]
    r = i[1]
    print(ans[r-1] - ans[l-1])

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

for x in lr:
    ans = 0
    l = x[0]
    r = x[1]
    a = s[l-1:r]
    for i in range(r-l):
        if a[i] == "A" and a[i+1] == "C":
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = 1
        pre = s[i]
    for _ in range(q):
        l, r = map(int, input().split())
        print(sum(t[l:r]))
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = 1
        pre = s[i]
    t = np.array(t)
    for _ in range(q):
        l, r = map(int, input().split())
        print(sum(t[l:r]))
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    lr =  [list(map(int, input().split())) for _ in range(q)]
    
    t = [0] * n
    pre = s[0]
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = 1
        pre = s[i]
    for l, r in lr:
        print(sum(t[l:r]))
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    lr =  [list(map(int, input().split())) for _ in range(q)]
    
    for l, r in lr:
        print(s[l-1:r].count('AC'))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = input()
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
A = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        A[i] = 1
for i in range(q):
    print(sum(A[LR[i][0]-1:LR[i][1]-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())
    S_tmp = S[l-1:r]
    S_tmp = S_tmp.replace("AC", "@")
    print(S_tmp.count("@"))

Submission status: Time Limit Exceeded

Solution code:
import re

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

for target in targets:
    l, r = target
    s = S[l - 1:r]
    print(len(re.findall("AC", s)))

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:
N,Q = map(int, input().split())
S = input()
T = [0]*N
for i in range(1, N):
    if S[i -1: i +1] == "AC":
        T[i] += 1
for j in range(Q):
    l, r = map(int, input().split())
    print(sum(T[l : r]))

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-1):
  if S[i] == 'A' and S[i+1] == 'C':
    A[i] = 1
for i in range(Q):
  l, r = map(int, input().split())
  T = A[(l-1):(r-1)]
  ans = sum(T)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
A = [0 for i in range(N)]
a = 0
if S[0] == 'A':
  a = 1
for i in range(1,N):
  if a == 1 and S[i] == 'C':
    A[i] = 1
    a = 0
  if S[i] == 'A':
    a = 1
  else:
    a = 0
for i in range(Q):
  l, r = map(int, input().split())
  T = A[l:r]
  ans = sum(T)
  print(ans)

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())
  T = S[(l-1):r]
  n = len(T)
  a = 0
  ans = 0
  if T[0] == 'A':
    a = 1
  for j in range(1,n):
    if a == 1 and T[j] == 'C':
      ans += 1
      a = 0
    if T[j] == 'A':
      a = 1
    else:
      a = 0
  print(ans)

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

I = [i+1 for i in range(n) if i+2 < n and s[i:i+2] == "AC"]

for l,r in lr:
  cnt = 0
  for i in I:
    if l<=i<=r and l<=i+1<=r: cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

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

for l,r in lr:
  S = s[l-1:r]
  print(S.count("AC"))

Submission status: Time Limit Exceeded

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

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    print(S[int(query[i][0])-1:int(query[i][1])].count('AC'))

Submission status: Time Limit Exceeded

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

for i in range(Q):
    tmp = S[int(query[i][0])-1:int(query[i][1])]
    print(len([i for i in range(len(tmp)-1) if tmp[i] == 'A' and tmp[i+1] == 'C']))

Submission status: Time Limit Exceeded

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

for n in range(N-1):
  if S[n] == "A" and S[n+1] =="C":
    T[n] += 1

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

Submission status: Time Limit Exceeded

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

lac = list()
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        lac.append(i)


for i in range(q):
    l, r = map(int, input().split())
    print(sum(1 for x in lac if l-1 <= x <= r-2))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S = input()
ans = []
for i in range(Q):
    l,r = map(int, input().split())
    S_ = S[l-1:r]
    ans.append(S_.count("AC"))
print(*ans, sep="\n")

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

Submission status: Time Limit Exceeded

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

import re
import numpy as np

s = [i.span()[0] for i in list(re.finditer("AC", S))]
#print(s)

count = np.array([0] * (N+1))
for i in range(len(s)):
    count[s[i]+1:] += 1
    
#print(count)

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

print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r])
    
import re
    
for i in range(len(lr)):
    #print(S[lr[i][0]-1 : lr[i][1]])
    #print(re.findall("AC", S[lr[i][0]-1 : lr[i][1]]))
    #print(len(re.findall("AC", S[lr[i][0]-1 : lr[i][1]])))
    print(S[lr[i][0]-1 : lr[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):
    l, r = map(int, input().split())
    lr.append([l, r])
    
import re
    
for i in range(len(lr)):
    #print(S[lr[i][0]-1 : lr[i][1]])
    #print(re.findall("AC", S[lr[i][0]-1 : lr[i][1]]))
    print(len(re.findall("AC", S[lr[i][0]-1 : lr[i][1]])))

Submission status: Time Limit Exceeded

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

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

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

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 = [int(i) for i in input().split()]
S = input()

output = []
for i in range(Q):
    s, t = [int(i) for i in input().split()]
    cnt = S.count('AC', s-1, t)
    output.append(cnt)

for _ in output:
    print(_)

Submission status: Time Limit Exceeded

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

output = []
for i in range(Q):
    s, t = [int(i) for i in input().split()]
    string = S[s-1:t]
    cnt = 0
    for j in range(len(string)):
        partial_string = string[j:j+2]
        if partial_string == 'AC':
            cnt += 1
    output.append(cnt)

for _ in output:
    print(_)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = str(input())
ls = [list(map(int,input().split())) for _ in range(q)]
c = 0
a = []
for i in range(n-1):
    if s[i] == "A":
        if s[i+1] == "C":
            a.append(i)
for j in range(q):
    (u,t) = (ls[j][0],ls[j][1])
    for k in a:
        if k in range(u-1,t-1):
            c += 1
    print(c)
    c = 0

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = str(input())
ls = [list(map(int,input().split())) for _ in range(q)]
p = ""
k = 0
for i in range(q):
    for j in range(ls[i][0]-1,ls[i][1]-1):
        if s[j] == "A":
            if s[j+1] == "C":
                k += 1
    print(k)
    k = 0

Submission status: Time Limit Exceeded

Solution code:
#C
def f(x):
    return int(x) - 1

n, q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
    l[i], r[i] = map(f, input().split())
for i in range(q):
    count=0
    for j in range(l[i], r[i]):
        if r[i] == n:
            pass
        if s[j] == "A" and s[j + 1] == "C":
            count+=1
    print(count)

Submission status: Time Limit Exceeded

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

for l,r in questions:
    sub = s[l-1:r]
    print(sub.count('AC'))

Submission status: Time Limit Exceeded

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

ac = [0] * n
for i in range(n):
    ac[i] = s[:i+1].count("AC")

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,q=list(map(int,input().split()))
s=input()
cnt=0
t=[0]*n

for i in range(n-2):
  t[i]=s[i:i+2].count("AC")
#print(t)

for i in range(q):
  n,q=list(map(int,input().split()))
  print(sum(t[n-1:q-1]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

#print(C)

for q in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1

  ans = sum(C[l:r])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys


def main():
  readline = sys.stdin.readline
  
  n, q = map(int, readline().rstrip().split())
  s = readline().rstrip()
  indexes = tuple((m.span())[0] for m in re.finditer('AC', s))
  
  for _ in range(q):
    l, r = map(int, readline().rstrip().split())
    print(len(list(filter(lambda i: l - 1 <= i and i < r - 1, indexes))))


if __name__ == "__main__":
  main()

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())
    t=s[l-1:r]
    c=0
    for a,b in zip(t,t[1:]):
        if a=='A' and b=='C':
            c+=1
    print(c)

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:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, q = input_list()
    s = input()
    for _ in range(q):
        l, r = input_list()
        ss = s[l-1:r]
        print(ss.count('AC'))


def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, q = map(int, readline().split())
    s = readline().rstrip().decode()
    
    for _ in range(q):
        l, r = map(int, readline().split())
        print(s[l-1:r].count('AC'))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N,Q = (int(x) for x in input().split())
S =input().strip()
l =[]
r =[]
for i in range(Q):
    l1,r1 = (int(x) for x in input().split())
    l.append(l1 -1)
    r.append(r1-2) #"AC"のAの位置と比べるため－２

# ACのindex(左端)
import re
import numpy as np
x =[m.start() for m in re.finditer('AC', S)]
x =np.array(x)
#
for i in range(Q):
    ans = np.count_nonzero( (x >=l[i]) & (x <=r[i]) )
    print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = input()
cnt = 0
for _ in range(q):
    r,l = map(int,input().split())
    bubun = s[r-1:l]
    print(bubun.count("AC"))

Submission status: Time Limit Exceeded

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

ans = []

for i in range(q):
    l, r = map(int, input().split())
    S = s[l - 1:r]
    ans.append(S.count("AC"))

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,q,s,l):
    lst_ac = [0]*(len(s)-1)
    for i in range(len(s)-1):
        if s[i]+s[i+1] == "AC":
            lst_ac[i] = 1
    for item in l:
        print(sum(lst_ac[item[0]-1:item[1]-1]))

def resolve():
    n,q = mi()
    s = input()
    l = mix(q)
    main(n,q,s,l)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,q,s,l):
    res = []
    for i in l:
        c = 0
        tar = s[i[0]-1:i[1]]
        for j in range(len(tar)-1):
            if tar[j]=="A" and tar[j+1]=="C":
                c += 1
        res.append(c)
    for ans in res:
        print(ans)

def resolve():
    n,q = mi()
    s = input()
    l = mix(q)
    main(n,q,s,l)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


resolve()

Submission status: Time Limit Exceeded

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

dp = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        dp[i][j]=len(re.findall(r'AC',s[i:j+1]))

for i in range(q):
    print(dp[L[i]-1][R[i]-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())
    print(S[l-1:r].count("AC"))

Submission status: Time Limit Exceeded

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

# check
counts = []
c_append = counts.append
for i in range(Q):
    l, r = map(int, input().split())
    AC_cnt = S.count("AC", l - 1, r) 
    c_append(AC_cnt)

# output
for c in counts:
    print(c)

Submission status: Time Limit Exceeded

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

# check
counts = []
c_append = counts.append
for i in range(Q):
    l, r = map(int, input().split())
    substr = S[l - 1:r]
    AC_cnt = substr.replace("AC", "*").count("*")
    c_append(AC_cnt)

# output
for c in counts:
    print(c)

Submission status: Time Limit Exceeded

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

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

# check
for substr in substrs:
    substr_len = len(substr)
    AC_cnt = substr.replace("AC", "*").count("*")

    print(AC_cnt)

Submission status: Time Limit Exceeded

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

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

# check
for l, r in index:
    check_substr = S[l:r]
    substr_len = len(check_substr)
    AC_cnt = sum(
        [
            1
            for i in range(0, substr_len - 1)
            if check_substr[i:i + 2] == "AC"
        ]
    )

    print(AC_cnt)

Submission status: Time Limit Exceeded

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

d= {}

for k in range(n):
    d[k]=0

for j in range(n):
    if j ==n-1:
        tmp_str = s[j]
    else:
        tmp_str = s[j:]

    d[j] += tmp_str.count('AC')

# print(d)

ans = []
for _ in range(q):
    l,r = map(int,input().split())

    ans.append(d[l-1] -d[r-1])


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

d= {}

for k in range(n-1):
    d[k]=0

for j in range(n-1):
    if s[j:j+2]=='AC':
        d[j]+=1

# print(d)

ans = []
for _ in range(q):
    l,r = map(int,input().split())

    tmp = 0
    for p in range(l-1 , r-1):
        tmp+=d[p]

    ans.append(tmp)



for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

ans = []
for _ in range(q):
    l,r = map(int,input().split())

    tmp_str = s[l-1:r]

    ans.append( tmp_str.count('AC') )

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
check = [0]*n
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = 1
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r):
        ans += check[j]
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(x) for x in input().split())
string = list(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = (int(x) for x in input().split())

for i in range(q):
    count = 0
    for j in range(r[i]-l[i]):
        if string[l[i]+j-1] == 'A' and string[l[i]+j] == 'C':
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
A=[]
for t in range(Q):
    l,r=map(int,input().split())
    T=S[l-1:r]
    cnt=0
    for k in range(len(T)-1):
        if T[k:k+2]=='AC':
            cnt+=1
        else:
            continue
    A.append(cnt)
for s in A:
    print(s)

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 = input()
queries = tuple(tuple(map(int, input().split(' '))) for _ in range(Q))

ac_indexes = set()
for i in range(N - 1):
    if S[i:i + 2] == 'AC':
        ac_indexes.add(i + 1)

for left, right in queries:
    count = 0
    for i in range(left, right):
        count += int(i in ac_indexes)
    print(count)

Submission status: Time Limit Exceeded

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

pre = ''
hit = []
for i, s in enumerate(S):
  if pre=='A' and s=='C':
    hit.append(i)
  pre = s
  
for _ in range(Q):
  l, r = [int(i) for i in input().strip().split()]
  print(sum([1 for h in hit if l<=h<r]))

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    s = input()
    ll = [0]*n
    rl = [0]*n
    lr = []

    for i in range(n):
        ll[i] = s[:i + 1].count("AC")
        rl[i] = s[i:].count("AC")

    for i in range(q):
        l, r = map(int, input().split())
        l = max(l - 1, 0)
        lr.append([l , r - 1])

    for i, j in lr:
        ans = rl[0] - ll[i] - rl[j]
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
ll = [0]*n
rl = [0]*n
lr = []

for i in range(n):
    ll[i] = s[:i + 1].count("AC")
    rl[i] = s[i:].count("AC")

for i in range(q):
    l, r = map(int, input().split())
    l = max(l - 1, 0)
    lr.append([l , r - 1]) 



for i in range(q):
    ans = rl[0] - ll[lr[i][0]] - rl[lr[i][1]]
    print(ans)

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())
    if r == len(s):
        print(s[l -1:].count('AC'))
    else:
        print(s[l - 1: r].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
x,y= list(map(int, input().split()))
n=input()
for k in range(y):
    i,j= list(map(int, input().split()))
    i-=1
    ans=n.count('AC', i, j)
    print(ans)

Submission status: Time Limit Exceeded

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

ansLis = [0]
line = ""
for i in range(N):
    line += S[i]
    ansLis.append(line.count("AC"))
# print(ansLis)

ans = []
for _ in range(Q):
    l,r = map(int,input().split())
    num = ansLis[r] - ansLis[l]
    # if S[l-2] == "A" and S[l-1] == "C":
    #     num = max(0, num-1)
    ans.append(num)

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

Submission status: Time Limit Exceeded

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

ansLis = []
for i in range(N+1):
    ansLis.append(S[:i].count("AC"))
# print(ansLis)

ans = []
for _ in range(Q):
    l,r = map(int,input().split())
    num = ansLis[r] - ansLis[l]
    # if S[l-2] == "A" and S[l-1] == "C":
    #     num = max(0, num-1)
    ans.append(num)

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

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=str(input())
s=list(s)
a=[0]*n
for i in range(0,n):
  temp=s[i:]  
  temp="".join(temp)
  a[i]=temp.count("AC")
for i in range(0,q):
  l,r=map(int,input().split())
  print(a[l-1]-a[r-1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=str(input())
s=list(s)
for i in range(0,q):
  l,r=map(int,input().split())
  temp=s[l-1:r]
  temp="".join(temp)
  temp2=temp.replace("AC","")
  print(int((len(temp)-len(temp2))/2))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=str(input())
s=list(s)
for i in range(0,q):
  l,r=map(int,input().split())
  temp=s[l-1:r]
  temp="".join(temp)
  print(temp.count("AC"))

Submission status: Time Limit Exceeded

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

ac = [False] * (n-1)
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        ac[i] = True

for i in range(q):
    print(sum(ac[l[i]-1: r[i]-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    # l = list()
    # r = list()
    s_list = list()
    # s_tuple = tuple()
    for _ in range(q):
        l_i, r_i = map(int, input().split())
        # l.append(l_i)
        # r.append(r_i)
        s_list.append(s[l_i - 1:r_i])
        # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    
    s_tuple = tuple(s_list)

    for i in s_tuple:
        print(i.count('AC'))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    # l = list()
    # r = list()
    s_list = list()
    # s_tuple = tuple()
    for _ in range(q):
        l_i, r_i = map(int, input().split())
        # l.append(l_i)
        # r.append(r_i)
        s_list.append(s[l_i - 1:r_i])
        # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
        s_tuple = tuple(s_list)

    for i in s_tuple:
        print(i.count('AC'))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for _ in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in s_list:
    print(i.count('AC'))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for _ in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in range(q):
    print(s_list[i].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for i in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in range(q):
    print(s_list[i].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for i in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in range(q):
    print(s_list[i].count('AC'))

Submission status: Time Limit Exceeded

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

for i in range(q):
    s_i = s[l[i]-1:r[i]]
    print(s_i.count('AC'))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
memo = defaultdict(int)
for i in range(1, N+1):
    memo[i] = S[:i].count('AC')
for l, r in lr:
    print(memo[r] - memo[l])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = input()
lr_list = [list(map(int,input().split())) for nesya in range(q)]
ac_set = set()
t = s.replace('AC',' AC')
s_list = list(t.split(' '))
c = len(s_list.pop(0))+1
ac_set.add(c)
for hoge in s_list:
  c += len(hoge)
  ac_set.add(c)
for lr in lr_list:
  ans = 0
  for i in range(lr[0],lr[1]):
    if i in ac_set:
      ans += 1
  print(ans)