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: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int,input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for _ in range(Q):
  l, r = map(int,input().split())
  print(t[r-1] - t[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:




import numpy as np

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

a = np.zeros(N)
   
for i in range(1,N):
    if (S[i-1] == "A")and(S[i] == "C"):
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
        
for i in range(Q):
    l, r = map(int, input().split())
    print(int(a[r-1] - a[l-1]))

Submission status: Accepted

Solution code:
#coding: utf-8
N, Q = map(int, input().split())
S = input()
T = [0]
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        T.append(T[i] + 1)
    else:
        T.append(T[i])
for j in range(Q):
    l, r = map(int, input().split())
    print(T[r-1] - T[l-1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
lr=[input() for __ in range(q)]
cs=[0]*(n+1)

#端がACで-1で止まる文字列指定は大丈夫？.
for i in range(n):
    cs[i+1]=cs[i] + (1 if s[i:i+2] == 'AC' else 0)

for num in lr:
    l,r=map(int,num.split())
    print(cs[r-1] - cs[l-1])

Submission status: Accepted

Solution code:
import bisect
import re
import sys

N, Q = map(int, input().split())
S = sys.stdin.readline()
P = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

r = re.compile('AC')
a = [x.start() for x in r.finditer(S)]

if a:
    for q in P:
        p1 = bisect.bisect_left(a, q[0] - 1)
        p2 = bisect.bisect_right(a, q[1] - 2)
        print(p2 - p1)
else:
    for q in P:
        print(0)

Submission status: Accepted

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

Submission status: Accepted

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

accum = [0] * N

def countAC():
    count = 0
    for i in range(1, N):
        if(S[i-1] == "A" and S[i] == "C"):
            count += 1
        accum[i] = count



countAC()

for i in range(Q):
    print(accum[LR[i][1]-1] - accum[LR[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = str(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
# 累積和をもとめておく
count = [0]*(N)
for i in range(1, N):
    if S[i]=='C' and S[i-1]=='A':
        count[i] = count[i-1] + 1
    else:
        count[i] = count[i-1]
for l, r in LR:
    print(count[r-1]-count[l-1])

Submission status: Accepted

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] = T[i-1] + 1
    else:
        T[i] = T[i-1]
for j in range(Q):
    left, right = map(int, input().split())
    print(T[right-1]-T[left-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = str(input())
s = "x" + s + "x" + "x"
n += 3
left = [0 for i in range(n-1)]
num = 0

for i in range(n-2):
    if s[i:i+2] == "AC":
        left[i] += 1
        num += 1
    left[i+1] = left[i]

right = [0 for i in range(n-1)]
for i in range(n-2):
    if s[-(2+i):-i] == "AC":
        right[-(1+i)] += 1
    right[-(2+i)] = right[-(1+i)]
for i in range(q):
    a,b = map(int,input().split())
    print(num-left[a-1]-right[b])

Submission status: Accepted

Solution code:
import bisect
import re

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

r = re.compile('AC')
a = [x.start() for x in r.finditer(S)]

if a:
    for q in P:
        p1 = bisect.bisect_left(a, q[0] - 1)
        p2 = bisect.bisect_right(a, q[1] - 2)
        print(p2 - p1)
else:
    for q in P:
        print(0)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
list1=[list(map(int,input().split())) for _ in range(Q)]
list2=[0]*(N+1)
count=0
for i in range(N):
    if i>0:
        list2[i+1]=list2[i]
    if i==N-1:
        continue
    elif S[i:i+2]=="AC":
        list2[i+1]+=1
for tmp in list1:
    print(list2[tmp[1]-1]-list2[tmp[0]-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
p = [0]*(N)
a = 0
for i in range(-1,N-2):
    if S[i+1] == "A" and S[i+2]=="C":
        a+=1
    p[i+2]=a
#print(p)
for i in range(Q):
    a,b = map(int,input().split())
    print(p[b-1] - p[a-1])

Submission status: Accepted

Solution code:

[N,Q] = list(map(int,input().split()))
locate= [-1]*N

str=input()
s = list(str)

num_a=[0]*N
tmp=0

for i in range(1,N):
    if s[i-1]=='A' and s[i]=='C':
        tmp+=1
    num_a[i]=tmp
        

for i in range(Q):
    a = list(map(int, input().split()))
    L=a[0]-1
    R=a[1]-1
    print(num_a[R]-num_a[L])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

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

ac_idx = [0]
count = 0

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

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

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
n,q=I()
s=input()
a=[0]
for i in range(n):a+=[a[i]+(s[i-1:i+1]=='AC')]
for _ in[0]*q:l,r=I();print(a[r]-a[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
I=lambda:map(int,input().split())
N,Q=I()
S=input()
m=[]
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        m += [i]
#print(m)
for i in range(Q):
    l,r=I()
    if m==[]:print(0);continue
    li=bisect.bisect_left(m,l-1)
    ri=bisect.bisect_left(m,r-1)
    #print(i,li,ri)
    print(ri-li-1 if m[ri-1]==r else ri-li)

Submission status: Accepted

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

    list = [0] * (N + 1)

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

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
nq = list(map(int, input().split()))
n = nq[0]
q = nq[1]
s = list(input())
l = []
r = []

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

hairetu = [0]
toukei = 0

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

hairetu.append(toukei)

for i in range(q):
    if hairetu[l[i] - 1] != hairetu[l[i]]:
        print(hairetu[r[i] - 1] - hairetu[l[i]] + 1)
    else:
        print(hairetu[r[i] - 1] - hairetu[l[i]])

Submission status: Accepted

Solution code:
#累積和　なるほど！

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

ac = [0]*n
#012345678
# ACACTACG
# 01122233

for i in range(1,n):
	if s[i-1:i+1] =='AC':
		ac[i] = ac[i-1] + 1
	else:
		ac[i] = ac[i-1]

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

	print(answer)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import itertools
import re
import sys
sys.setrecursionlimit(10**8)
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    N, Q = map(int, input_string[0].split())
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    t=[0]*(N+1)
    for i in range(N):
        t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
    #for i in range(Q):
    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]))
        #totalCnt = cntAC(L, R, S)
        totalCnt = t[r-1] - t[l-1]
        print(totalCnt)
    return
 

"""
wrong answer
def cntAC(l, r, D, S, cnt):
    global dp
    global T
    if r-l == D+1:
        return cnt
    if str(l)+str(r) not in T:
        T[str(l)+str(r)] = S[l-1:r]
        t = T[str(l)+str(r)]
    if str(l)+str(r) not in dp:
        #print(t)
        dp[str(l)+str(r)] = len(t.split('AC'))-1
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
    else:
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
"""
 

"""
wrong answer
def cntAC(L, r, S):
    global dp
    global T
    for l in range(L, r)[::-1]:
        if str(l)+str(r) not in T:
            T[str(l)+str(r)] = S[l-1:r]
            t = T[str(l)+str(r)]
        else:
            t = T[str(l)+str(r)]
        if str(l)+str(r) not in dp:
            dp[str(l)+str(r)] = len(t.split('AC'))-1
            cnt = dp[str(l)+str(r)]
        else:
            cnt = dp[str(l)+str(r)]
    return cnt
"""
 
def cntAC(L, R, S):
    cnt = 0
    for l in range(L, R):
        t = S[l-1:l+1]
        cnt +=  1 if t == 'AC' else 0
    return cnt

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
x = [0 for i in range(N)]
A = False
for i in range(len(S)):
    c = S[i]
    if c == 'A':
        A = True
    elif A and c == 'C':
        x[i] += 1
        A = False
    else:
        A = False
s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = s[i]+x[i]
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    if s[l] != s[l+1]:
        print(s[r]-s[l]-1)
    else:
        print(s[r]-s[l])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=list(input())
A=[list(map(int,input().split()))for i in range(q)]
total=[0]*(n+1)#累積和をとる配列
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        total[i+1]=total[i]+1
    else:
        total[i+1]=total[i]
for i in range(q):
    print(total[A[i][1]]-total[A[i][0]])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

# ACが来たらカウントする
dp = [0] * N
for i in range(1, N):
    s = S[i - 1] + S[i]
    if s == "AC":
        dp[i] += 1

# 累積和
DP = list(accumulate(dp))

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

Submission status: Accepted

Solution code:
import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
S = input()
question_list = []

for i in range(Q):
    l, r = map(int, input().split())
    question_list.append((l, r))

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

for lr in question_list:
    l = lr[0]
    r = lr[1]
    num = total_list[r - 1] - total_list[l - 1]
    print(num)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
ACsuu=[0 for i in range(n)]
for i in range(1,n):
  ACsuu[i]=ACsuu[i-1]+(1 if s[i-1:i+1]=="AC" else 0)
for i in range(m):
  a,b=map(int,input().split())
  print(ACsuu[b-1]-ACsuu[a-1])

Submission status: Accepted

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]

S_tf = [0]*(N+1)
for ind in range(N):
    S_tf[ind + 1] = S_tf[ind] + (1 if S[ind:ind+2] == "AC" else 0)
for ind in range(Q):
    print(S_tf[max(0, r[ind]-1)] - S_tf[min(l[ind]-1, N)])

Submission status: Accepted

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

AC_list = [0] * (N+1)
 
val=0
for i in range(N-1):
    if(S[i+1]=="C"):
        if(S[i]=="A"):
            val +=1

    AC_list[i+1] = val
AC_list[i+2] = val

for i in range(Q):
    l, r = (int(_) for _ in input().split())
    if(r!=N):
        if(S[r-1]=="A" and S[r]=="C"):
            print(AC_list[r]-AC_list[l-1]-1)
        else:
            print(AC_list[r]-AC_list[l-1])
    else:
        print(AC_list[r]-AC_list[l-1])

Submission status: Accepted

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

for k in range(q):
    print(ls[A[k][1]-1]-ls[A[k][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
s = input()
nlis = [0]
cnt = 0
for i in range(len(s)-1):
    if(s[i:i+2] == "AC"): 
        cnt += 1
    nlis.append(cnt)
#print(nlis)
for i in range(Q):
    in0, in1 = map(int, input().split())
    print(nlis[in1-1]-nlis[in0-1])

Submission status: Accepted

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

ACnum = [0]
for i in range(N - 1):
    ACnum.append(ACnum[-1])
    if("AC" == S[i:i + 2]):
        ACnum[i + 1] += 1
#print("ACnum = {}".format(ACnum))

for l, r in lr:
    print(str(ACnum[r - 1] - ACnum[l - 1]))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)

Submission status: Accepted

Solution code:
def have_AC(str):
    count=[0]
    for i in range(1,len(str)):
        if(str[i]=='C' and str[i-1]=='A'):
            count.append(count[i-1]+1)
            continue
        count.append(count[i-1])
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]
d=have_AC(s)

for i in range(q):
    a,b=input().split()
    a=int(a)
    b=int(b)
    num.append(d[b-1]-d[a-1])

for j in range(len(num)):
    print(num[j])

Submission status: Accepted

Solution code:
import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split(" "))
S = input()
t = [0]*(N+1)
#N+1個の0を持つリスト
for i in range(N):
    if S[i:i+2] == "AC":
        #S[x, y]は文字列Sのx番目からy-1番目までの文字列
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]
#S=0123...
#T=0123...

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
#l, r = 123...
#r番目までのときのACの数はt[r-1]

Submission status: Accepted

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

Submission status: Accepted

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

cumul = [0]*len(S)
cnt = 0
for i in range(len(S)-1):
    cumul[i] = cnt
    if S[i]=='A':
        if S[i+1] == 'C':
            cnt+=1
cumul[-1]=cnt

ret = []
for i in range(Q):
    l, r = map(int, input().split())
    cnt = cumul[r-1] - cumul[l-1]
    ret.append(str(cnt))
print('\n'.join(ret))

Submission status: Accepted

Solution code:
import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline
n, q = map(int, input().split())
s = input()
flag = 0 
check_list = []
cnt = 0
for i in range(n):
    if flag == 1:
        if s[i] == 'A':
            flag = 1
        elif s[i] == 'C':
            cnt += 1
            flag = 0
        else:
            flag = 0
    else:
        if s[i] == 'A':
            flag = 1
        else:
            flag = 0
    check_list.append(cnt)
for _ in range(q):
    l, r = map(int, input().split())
    print(check_list[r-1]-check_list[l-1])

Submission status: Accepted

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

for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=='AC' else 0)

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

Submission status: Accepted

Solution code:
def get():
    a=input()
    b=[int(i) for i in a.split()]
    return b[0],b[1]

n,q=get()
s=input()

a=[0]
b=[]

for i in range(n-1):
    if s[i:i+2]=="AC":
        a.append(a[-1]+1)
        b.append(1)
    else:
        a.append(a[-1])
        b.append(0)

for i in range(q):
    l,r=get()
    l-=1
    r-=1
    print(a[r]-a[l])

Submission status: Accepted

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

for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=='AC' else 0)

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

Submission status: Accepted

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

ac_list  = [0]*N
cnt = 0
for i in range(N-1):
    if i < len(S) and S[i:i+2] == "AC":
        cnt += 1
    ac_list[i+1] = cnt
        
for lr in lr_list:
    print(ac_list[lr[1]-1] - ac_list[lr[0]-1])

Submission status: Accepted

Solution code:
target_str = "AC"

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

cumsum_list = [0 for i in range(N)]

cnt = 0
for i in range(N - 1):
  if S[i: i + 2] == target_str:
    cnt += 1
  cumsum_list[i] = cnt
cumsum_list.insert(0, 0)
cumsum_list.insert(0, 0)


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

Submission status: Accepted

Solution code:
import re

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

array = [0 for i in range(N + 1)]
for i in range(N) :
    array[i + 1] = array[i] + (1 if S[i: i + 2] == 'AC' else 0)

for i in range(Q) :
    print(array[L[i][1] - 1] - array[L[i][0] - 1])

Submission status: Accepted

Solution code:
def get_ac_count(S):
    buf = None
    temp = []
    count = 0
    for c in S:
        if c == "A":
            buf = "A"
        elif buf == "A" and c == "C":
            buf = None
            count += 1
        elif buf == "A":
            buf = None
        temp.append(count)
    return temp
N, Q = map(int, input().split())
S = input()
ac_count = get_ac_count(S)
for i in range(Q):
    l,r = map(int, input().split())
    print(ac_count[r-1]-ac_count[l-1])

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, q = map(int, input().split())
    s = input()
    acc = [0] * (n + 1)
    for i in range(1, n):
        acc[i + 1] = acc[i]
        if s[i - 1:i + 1] == 'AC':
            acc[i + 1] += 1
    for l, r in (tuple(int(s) for s in input().split()) for _ in range(q)):
        print(acc[r] - acc[l])

Submission status: Accepted

Solution code:
from sys import exit

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

S = input()

AC = [0] * N

c = 0

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

for _ in range(Q):
    li, ri = map(int, input().split())
    print(AC[ri - 1] - AC[li - 1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin

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

list_out = [0] * N
cnt = 0
f = 0

# AC文字列のAの位置をリストに収めた
for i in range(len(S)):
  if S[i] == 'A':
    f = 1
    list_out[i] = list_out[i-1]    
  elif S[i] == 'C':
    if f == 1:
      cnt += 1
      f = 0
      list_out[i] = cnt
    else:
      list_out[i] = list_out[i-1]
  else:
    f = 0
    list_out[i] = list_out[i-1]    


# 指定した文字列範囲を含む要素数を表示
for i in se:
  print(list_out[i[1]-1] - list_out[i[0]-1])

Submission status: Accepted

Solution code:
""" AtCoder """

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

tmp = 0
l = [0]

for i in range(1, N):
    if S[i - 1] + S[i] == "AC":
        tmp += 1
    l.append(tmp)

for i in range(Q):
    print(l[lr[i][1]-1] - l[lr[i][0]-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])

Submission status: Accepted

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

# cumsum
A_list = [0]*(N+1)
C_list = [0]*(N+1)
for i in range(N-1):
    if S[i:i+2] == "AC":
        A_list[i+1] = 1
        C_list[i+2] = 1
A_ = 0
C_ = 0
for i in range(N+1):
    A_ += A_list[i]
    A_list[i] = A_
    C_ += C_list[i]
    C_list[i] = C_
    
res_list = []
for _ in range(Q):
    i, j = map(int, input().split())
    a_cnt = A_list[j] - A_list[i-1]
    c_cnt = C_list[j] - C_list[i-1]
    res_list.append(C_list[j] - A_list[i-1])
    
for r in res_list:
    print(r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 20:45:14 2019

@author: screamLab
"""

n,m = input().split()
s = input()
ans = 0
table = [0]
for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ans += 1
    table.append(ans)
        
for i in range(int(m)):
    a,b = input().split()
    a = int(a)
    b = int(b)
    print(table[b-1] - table[a-1])

Submission status: Accepted

Solution code:
def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


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

Submission status: Accepted

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)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])

Submission status: Accepted

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

a_loc = [0] * (N + 1)
for i in range(N):
    a_loc[i+1] = a_loc[i] + (1 if S[i:i+2] == 'AC' else 0)

ans = [0] * Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    ans[i] = a_loc[r-1] - a_loc[l-1]
    
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * N
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 2
    r_i = r[q] - 2

    if l_i < 0:
        c_l = 0
    else:
        c_l = cumsum[l_i]
    if r_i < 0:
        c_r = 0
    else:
        c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

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

Submission status: Accepted

Solution code:
n,q=list(map(int,input().split()))
b=input()
k=[0]*n
ac=0
for i in range(n-1):
  ac += 1 if b[i:i+2] == 'AC' else 0
  k[i]=ac
for i in range(q):
  l,r = list(map(int,input().split()))
  print(k[r-2]-k[l-2])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = (input())
cnt = [0] * (N + 1)
for i in range(N):
 if S[i:i+2] == "AC":
  cnt[i+1] = cnt[i] + 1
 else:
  cnt[i+1] = cnt[i]

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

Submission status: Accepted

Solution code:
N,Q = [int(x) for x in input().split()]
S = input()
l = [0]*Q
r = [0]*Q
li = [0]*(N+1)
for i in range(Q):
    l[i],r[i] = [int(x) for x in input().split()]
state = 0
for index,j in enumerate(S):
    li[index+1]=li[index]
    if(state == 1):
        if(j == 'C'):
            li[index+1]+=1
        state = 0
    if(j == 'A'):
        state = 1
        
for i in range(Q):
    print(li[r[i]]-li[l[i]])

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
N,Q=I()
S=input()
m=[0]
for i in range(N-1):
    m+=[m[-1]+(1 if S[i:i+2]=='AC' else 0)]
#print(m)
for i in range(Q):
    l,r=I()
    print(m[r-1]-m[l-1])