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:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,q = [int(i) for i in readline().split()]
s = input()+"G"
lr = [[int(i)-1 for i in readline().split()] for _ in range(q)]

res = [0]*(n+1)

for i,c in enumerate(s[:-1]):
    res[i+1] = res[i] + (1 if s[i]=="A" and s[i+1] == "C" else 0)

for l,r in lr:
    ans = res[r+1] - res[l]
    if  s[r]=="A" and s[r+1] == "C":
        ans -= 1
    print(ans)
    

#print(s)
#print(res)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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 = lr[i][0]-1, lr[i][1]-1
    print(t[r] - t[l])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = "Z" + input()
cumsum = [0] * (N + 1)
for i in range(1, N + 1):
  temp = S[i - 1] == "A" and S[i] == "C"
  cumsum[i] = cumsum[i - 1] + temp
#print(cumsum)
for _ in range(Q):
  l, r = map(int, input().split())
  temp = S[l - 1] == "A" and S[l] == "C"
  print(cumsum[r] - cumsum[l - 1] - temp)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
c1=[1 if (s[i]=="A" and s[i+1]=="C") else 0 for i in range(n-1) ]
#print(c1)
d=[list(map(int,input().split())) for i in range(q)]
c2=[0]*n
for i in range(1,n):
    #print(i)
    c2[i]=c2[i-1]+c1[i-1]
#print(c2)
for i in range(q):
    print(c2[d[i][1]-1]-c2[d[i][0]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

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

Submission status: Accepted

Solution code:
def MAP(): return map(int,input().split())

n,q = MAP()
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()
    print(t[r-1]-t[l-1])

Submission status: Accepted

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

count_AC = [0]
index_A = -2
sum_AC = 0
for i in range(n):
  if s[i] == 'A':
    index_A = i
  elif s[i] == 'C' and i == index_A + 1:
    sum_AC += 1
  count_AC.append(sum_AC)

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
I = [list(map(int,input().split())) for i in range(q)]
AC = []
ac = 0
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac += 1
        AC += [ac]
    else:
        AC += [ac]
AC = [0] + AC + [ac]
for i in range(q):
    ac_q =  AC[I[i][1]-1]-AC[I[i][0]-1]
    print(ac_q)

Submission status: Accepted

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

for i in range(1, n):
    s=S[i-1]+S[i]
    if s=="AC":
        cnt[i]+=1

for i in range(1, n):
    cnt[i]+=cnt[i-1]

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

Submission status: Accepted

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

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


main()

Submission status: Accepted

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

N, Q = map(int, readline().split())
S = readline()
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, readline().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

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

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

cum = [0] * N
c = 0
for i in range(0, N - 1):
    if S[i:i + 2] == "AC":
        c += 1

    cum[i + 1] = c
cum[-1] = c

for l, r in zip(L, R):
    print(cum[r - 1] - cum[l - 1])

Submission status: Accepted

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

C = [0] * N
cnt = 0
for n in range(1, N):
    if S[n - 1:n+1] == "AC":
        cnt += 1
    C[n] = cnt

for q in range(Q):
    l, r = LR[q]
    print(C[r-1] - C[l-1])

Submission status: Accepted

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

for i in range(1, n):
    if s[i - 1 : i + 1] == "AC":
        c[i] += 1
    c[i] += c[i - 1]

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

Submission status: Accepted

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

ans = [0] * q

for i in range(q):
    l, r = map(int, input().split())
    ans[i] = cum[r] - cum[l]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n, q = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    ss = [0] * n
    t = 0
    for i in range(n):
        if s[i] == "C" and s[i-1] == "A":
            t += 1
        ss[i] = t
    for l, r in [list(map(int, input().split())) for _ in range(q)]:
        print(ss[r-1] - ss[l-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = [0]*(N+1)
flag = 0
for i in range(N):
    if S[i] == "A":
        flag = 1
        A[i+1] = A[i]
    elif S[i] == "C" and flag == 1:
        A[i+1] = A[i] + 1
        flag = 0
    else:
        flag = 0
        A[i+1] = A[i]
for i in range(Q):
    l,r = LR[i]
    print(A[r] - A[l])

Submission status: Accepted

Solution code:
import bisect
n, q = map(int, input().split())
s = input()
t = []
for i in range(n-1):
  if s[i:i+2] == "AC":
    t.append(i+1)
for j in range(q):
  l, r = map(int, input().split())
  x = bisect.bisect_left(t, l)
  y = bisect.bisect_right(t, r-1)
  print(y-x)

Submission status: Accepted

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

dp = [float("inf") for i in range(N)]
dp[0] = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C" :
        dp[i] = dp[i-1] + 1
    else :
        dp[i] = dp[i-1]
val = [[] for i in range(Q)]
for i in range(Q) :
    a,b = map(int,input().split())
    val[i] = [a-1,b-1]
for i in range(Q):
    print("{}".format(dp[val[i][1]]-dp[val[i][0]]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC122 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
s = list(input())
lst = [0]*n
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        lst[i+1] = 1
lst = list(accumulate(lst))
for _ in range(q):
    l,r = LI()
    print(lst[r-1] - lst[l-1])

Submission status: Accepted

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

for i in range(1,N):
    C[i]=C[i-1]
    if S[i-1:i+1]=="AC":
        C[i]+=1

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

Submission status: Accepted

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

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

for i in range(Q):
    print(mLst[lLst[i][1] - 1] - mLst[lLst[i][0] - 1])

Submission status: Accepted

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

ACcount = [0 for _ in range(N)]
count = 0
Afound = False
for i in range(N):
    c = S[i]
    if c == "A":
        Afound = True
    else:
        if Afound and c == "C":
            count += 1
        Afound = False
    ACcount[i] = count

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

Submission status: Accepted

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


N, Q = map(int, input().split())
S = input().rstrip()
count_AC = [0]*N

have_A = False
count = 0
for i in range(N):
    if S[i] == 'A':
        have_A = True

    elif have_A:
        if S[i] == 'C':
            count += 1
            have_A = False
        else:
            have_A = False
    count_AC[i] = count

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

Submission status: Accepted

Solution code:
import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, q = map(int, input().split())
inputStr = map(str, input())
condi = getSomeInputListInt(q)

string = list(inputStr)

cnt = 0
cntArray = np.zeros(len(string))

tmpstring = []
for i in range(1, len(string)):
    if string[i-1]=="A" and string[i]=="C":
        cnt+=1
    cntArray[i] = cnt

for i in range(q):
    ans = cntArray[condi[i][1]-1] - cntArray[condi[i][0]-1]
    print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N,Q = map(int,input().split())
S = np.array(list('_' + input()), dtype='U2')
A = (S == 'A')
C = (S == 'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

for _ in range(Q):
    L,R = map(int,input().split())
    print(AC_cum[R-1] - AC_cum[L-1])

Submission status: Accepted

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

t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i : i + 2] == "AC" else 0)

for (l, r) in ls:
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t = [0] * N
for i in range(N - 1):
    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:
N,Q = map(int,input().split())

S = input()

add = [0] * (len(S)+1)

for i in range(N):
    if i==0:
        continue
    s = S[i]
    add[i] += add[i-1]
    if s == 'C':
        if S[i-1] == 'A':
            add[i] += 1

ret = []

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

    ret.append(ans)

for r in ret:
    print(r)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = [int(s) for s in input().split()]
text=input()
lst=[0 for s in range(N)]
for i in range(N+1):
  if(text[i-2:i]=='AC'):
    lst[i-1]=lst[i-2]+1
  else:
    lst[i-1]=lst[i-2]
for i in range(M):
  a,b = [int(s) for s in input().split()]
  print(max([lst[b-1]-lst[a-1],0]))

Submission status: Accepted

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

import heapq

def main(): 

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

    length = []
    cnt = 0
    length.append(cnt)
    for i in range(1,N):
        if S[i] == "C" and S[i-1] == "A":
            cnt += 1
        length.append(cnt)
    
    for i in range(Q):
        print(length[lr[i][1]-1]-length[lr[i][0]-1])


        


        


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ac = [0] * n
for i in range(1, n):
    ac[i] = ac[i-1] + int(s[i-1:i+1] == "AC")

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

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

left = [0] * n

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

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=input()
query=[list(map(int,input().split())) for i in range(q)]
x=[]
for i in range(n):
  if s[i:i+2]=='AC':
    x.append(i)
for i in range(q):
  x1=bisect.bisect_left(x,query[i][0]-1)
  x2=bisect.bisect_left(x,query[i][1]-1)
  print(x2-x1)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
query = [tuple(map(int, input().split())) for _ in range(q)]
cum = [0] * n
for i in range(n-1):
    cum[i+1] = cum[i] + int(s[i:i+2] == 'AC')

for l, r in query:
    print(cum[r-1] - cum[l-1])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  readline = stdin.readline
  n, q = map(int, readline().split())
  s = input()
  c = [0] * (n + 1)
  pch = s[0]
  pc = 0
  for i in range(2, n + 1):
    cch = s[i - 1]
    if cch == 'C' and pch == 'A':
      t = pc + 1
    else:
      t = pc
    c[i] = t
    pc = t
    pch = cch
  for _ in range(q):
    l, r = map(int, readline().split())
    t = c[r] - c[l - 1]
    if l >= 2 and s[l - 2: l] == 'AC':
      t -= 1
    print(t)
main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  readline = stdin.readline
  n, q = map(int, readline().split())
  s = input()
  c = [0] * (n + 1)
  for i in range(2, n + 1):
    if s[i - 1] == 'C' and s[i - 2] == 'A':
      c[i] = c[i - 1] + 1
    else:
      c[i] = c[i - 1]
  for _ in range(q):
    l, r = map(int, readline().split())
    t = c[r] - c[l - 1]
    if l >= 2 and s[l - 2: l] == 'AC':
      t -= 1
    print(t)
main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
flag = True
R = [0]*N
a = 0
for i in range(N):
    s = S[i]
    if s == "A":
        flag = True
    elif s == "C" and flag:
        a += 1
        flag = False
    else:
        flag = False
    R[i] = a
for i in range(Q):
    l, r = map(int, input().split())
    print(R[r-1] - R[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def get_ac(n,q,s,l,r):
    pos = [0]*n

    for j in range(0,n-1):
        if s[j] == 'A' and s[j+1] == 'C':
            pos[j+1] = pos[j] + 1
        else:
            pos[j+1] = pos[j]

    for i in range(q):
        left = l[i]
        right = r[i]
        count = pos[right - 1] - pos[left - 1]

        print count

if __name__ == '__main__':

    n,q = map(int,raw_input().split())
#    t1 = time.time()
    s = raw_input()

    l = [0]*q
    r = [0]*q

    for i in range(q):
        l[i],r[i] = map(int,raw_input().split())

#    t2 = time.time()
#    print('{0:.9f}'.format(t2 - t1))
    get_ac(n,q,s,l,r)

Submission status: Accepted

Solution code:
import bisect

n, q = map(int, input().split())
s=input()
sng=len(s)
aclist=[]
for i in range(sng-1):
    if s[i]=='A' and s[i+1]=='C':
        aclist.append(i+1)

#print(aclist)
for i in range(q):
    l, r = map(int, input().split())
    ll=bisect.bisect_left(aclist, l)
    rr=bisect.bisect_right(aclist, r-1)
    print(rr-ll)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
_, q = map(int, input().split())
s = input()
b = "B"
a = []
for i, c in enumerate(s) :
    if b+c == "AC" :
        a.append(i)
    b = c
for _ in range(q) :
    l, r = map(int, input().split())
    il = bisect_left(a, l)
    ir = bisect_right(a, r-1)
    print(ir-il)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
t=[0]*(n)
for i in range(n-1):
  t[i+1]=t[i]+(1 if s[i:i+2]=='AC' else 0)
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 = [int(x) for x in input().split(' ')]
s = input()
lr = [[int(x) for x in input().split(' ')] for _ in range(q)]


indexes = [0] * n

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

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
l=[0]*n
tmp="hoge"
for i,j in enumerate(s):
    if j=="C" and tmp=="A":
        l[i]=1
    tmp=s[i]
ls=[0]
tmp=0
for i in l:
    tmp+=i
    ls.append(tmp)
for i in range(q):
    a,b=map(int,input().split())
    print(ls[b]-ls[a])

Submission status: Accepted

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

    # i-th element count the number of AC in S[:i]
    prefix = [0, 0]
    prev = S[0]
    for i in range(1, N):
        if prev + S[i] == "AC":
            prefix.append(prefix[-2] + 1)
        else:
            prefix.append(prefix[-1])
        prev = S[i]

    for _ in range(Q):
        l, r = map(int, input().split())
        count = prefix[r] - prefix[l-1]
        if l > 1 and S[l-2] + S[l-1] == "AC":
            count -= 1
        print(count)

if __name__ == '__main__':
    # print(main())
    main()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline().strip()

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

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

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
i=0
d=""
while i<n-1:
	if s[i]=="A" and s[i+1]=="C":
		d+="0"*2
		i+=2
	else:
		d+=s[i]
		i+=1
d+=s[-1]
num=[0]*n
cnt=0
for i in range(n):
	if d[i]=="0":
		cnt+=1
	num[i]=cnt//2
for i in range(q):
	x,y=map(int,input().split())
	print(num[y-1]-num[x-1])

Submission status: Accepted

Solution code:

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

'''
累積和
t[1] = t[0] + (if S[0]からの2文字がACなら1 or 0) → AC の C 位置なら1
t[2] = t[1] + (if S[1]からの2文字がACなら1 or 0)
t[3] = t[2] + (if S[2]からの2文字がACなら1 or 0)
t[4] = t[3] + (if S[3]からの2文字がACなら1 or 0)
t[5] = t[4] + (if S[4]からの2文字がACなら1 or 0)
t[6] = t[5] + (if S[5]からの2文字がACなら1 or 0)
t[7] = t[6] + (if S[6]からの2文字がACなら1 or 0)
t[8] = t[7] + (if S[7]からの2文字がACなら1 or 0)

# 01234567
# ACACTACG
# 011222333
'''

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

#print(t)

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

    # 3, 7 なら、t[7-1] - t[3-1]
    #  → t[5]以下の数 - t[1]以下の数
    print(t[r-1] - t[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

for i 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()
L = []
L = [list(map(int, input().split())) for _ in range(q)]
A = [0, 0]
for i in range(n-1):
    A += A[-1]+(S[i:i+2] == "AC"),
for l, r in L: print(A[r]-A[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = list(input())
cusum = [0] * n
c = 0
lr = [[int(x) for x in input().split()] for _ in range(q)]
for i in range(n-1):
    cusum[i] = c
    if s[i:i+2] == ["A", "C"]:
        c += 1
        cusum[i+1] = c
cusum[n-1] = c

for j in range(q):
    l, r = lr[j]
    print(cusum[r-1] - cusum[l-1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
ac=[0 for _ in range(n)]
if n==1:
  for i in range(q):
    print(0)
    exit()

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

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

Submission status: Accepted

Solution code:
# ABC 122, c
n, q = [int(el) for el in 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 = [int(el) for el in input().split(' ')]
    print(T[r-1] - T[l-1])

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
S = str(input())
l,r = Line(Q)

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

for i in range(Q):
    print(a[l[i]-1]-a[r[i]-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

count_ac_list = [0] * n
for i in range(n-1):
    # print('{}: {}'.format(i, s[i:i+2]))
    if s[i:i+2] == 'AC':
        count_ac_list[i+1] = count_ac_list[i] + 1
    else:
        count_ac_list[i+1] = count_ac_list[i]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1]) for l, r in lr_list]

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

Submission status: Accepted

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

li = [0] * n
# print(s[0:2])
for i in range(n - 1):
  if s[i:i + 2] == "AC":
    li[i+1] += li[i] + 1
  else:
    li[i+1] = li[i]
# print(li)
for j in lr:
  print(li[j[1]-1] - li[j[0]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
a = [0] * n
for i in range(1, n):
    a[i] = a[i - 1]
    if (s[i - 1:i+1] == "AC"):
        a[i] += 1
for i 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 = list(input())
lr = [[] for i in range(q)]
for i in range(q):
  lr[i] =list(map(int,input().split()))

Sl = [0 for i in range(n+1)]
for i in range(1,n):
  if (S[i-1] == "A")&(S[i]=="C"):
    Sl[i] = Sl[i-1]+1
  else:
    Sl[i] = Sl[i-1]
Sl[n] = Sl[n-1]

ans = []
for i,j in lr:
  ans.append(Sl[j-1]-Sl[i-1])
  
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
# データ構造：ヒープ
import heapq
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)

# 定数
INF = float("inf")
MOD = int(1e9 + 7)
def int1(n):
    return int(n) - 1

# エントリーポイント
def main():
    N, Q = map(int, input().split())
    S = input()
    LR = tuple(map(int1, input().split()) for _ in range(Q))

    add_sum = [0]
    for n in range(1, N):
        add_sum += [add_sum[-1] + (S[n - 1:n + 1] == "AC")]

    for l, r in LR:
        print(add_sum[r] - add_sum[l])

main()

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

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

for i in range(q):
    print(exist[lr[i][1]-1]-exist[lr[i][0]-1])

Submission status: Accepted

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

for i in range(1,n):
  count_arr[i]=count_arr[i-1]+(1 if s[i-1]=='A' and s[i]=='C' else 0)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

n,q=map(int,input().split())
s=input()
l = [stdin.readline().rstrip().split() for _ in range(q)]

t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)
for j,k in l:
    print(t[int(k)-1]-t[int(j)-1])

Submission status: Accepted

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

Submission status: Accepted

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