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: Wrong Answer

Solution code:
# 累積和の考え方
#   listに積み重ねた数値を出しておくことで特定範囲の数値を求める時間を短縮する
#   例：ABBBBAABBBBAB があるときに(l,r)にAがいくつ含まれるかを求める場合は以下のように(1長い)listを作る
#      BBABBBAABBBBAA
#      000111123333345
#   このリストの文字列のr-lで出せる(3,7)ならstr[7]-str[3]を出すと3-1で2となる

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

# 累積和のリストを作成
cumsum = [0]*(n+1)
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        cumsum[i+1]+=cumsum[i]+1
    else:
        cumsum[i+1]=cumsum[i]
cumsum[n] = cumsum[n-1]

print(cumsum)
for left, right in lr:
    print(cumsum[right]-cumsum[left])

Submission status: Wrong Answer

Solution code:
# 累積和の考え方
#   listに積み重ねた数値を出しておくことで特定範囲の数値を求める時間を短縮する
#   例：ABBBBAABBBBAB があるときに(l,r)にAがいくつ含まれるかを求める場合は以下のように(1長い)listを作る
#      BBABBBAABBBBAA
#      000111123333345
#   このリストの文字列のr-lで出せる(3,7)ならstr[7]-str[3]を出すと3-1で2となる

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

# 累積和のリストを作成
cumsum = [0]*(n+1)
for i in range(1, n-1):
    if s[i-1] == 'A' and s[i] == 'C':
        cumsum[i+1]+=cumsum[i]+1
    else:
        cumsum[i+1]=cumsum[i]
cumsum[n] = cumsum[n-1]

for left, right in lr:
    print(cumsum[right]-cumsum[left])

Submission status: Wrong Answer

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

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

print(L)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
import re

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

indexes = [m.start() for m in re.finditer("AC", S)]

for target in targets:
    l, r = target
    bisect_l = bisect.bisect(indexes, l - 1)
    bisect_r = bisect.bisect_left(indexes, r - 1)
    if bisect_l == bisect_r:
        print(0)
    else:
        print(bisect_r - bisect_l + 1)

Submission status: Wrong Answer

Solution code:
#累積和的な

n,q = map(int,input().split())
s = input() + 'A' 
li = [0]*(n+1)

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

Submission status: Wrong Answer

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

li = [0]*n

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

from itertools import accumulate

lin = [0]+list(accumulate(li))
print(lin)
for _ in range(q):
    l,r = map(int,input().split())
    print(lin[r]-lin[l])

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
# 累積和
n,q = readInts()
Cum = [0] * (n+1)
S = input()
# 左にAがあるC
for i in range(1,n):
    if S[i-1] == 'A' and S[i] == 'C':
        Cum[i] += 1
for i in range(n):
    Cum[i+1] += Cum[i]
print(Cum)
for k in range(q):
    l,r = readInts()
    l -= 1
    r -= 1
    print(Cum[r] - Cum[l])

Submission status: Wrong Answer

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

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

print(lc)

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

Submission status: Wrong Answer

Solution code:
#ABC122C
def main():
    import sys
    S = sys.stdin.readline().rstrip()
    #print(S)
    cnt = 0
    ans = 0
    for s in S:
        if s in ['A', 'G', 'C', 'T']:
            cnt +=1
        else:
            ans = max(ans, cnt)
            cnt=0
    
    ans = max(ans, cnt)
    print(ans)   
            
                    
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


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

cac = [0]*(n+1)
for i in range(n):
    cac[i+1] = cac[i] + ac[i]

for i in range(q):
    l, r = map(int, input().split())
    ans = cac[r] - cac[l-1]
    if 0 < l-1 and s[l-2:l]=='AC':
            if r < n-2 and s[r-1:r+1]=='AC':
                ans-=2
    ans//=2
    print(ans)

Submission status: Wrong Answer

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

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)
print(t)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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 <= i and i < r, indexes))))


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, q = input_list()
    s = input()
    cumulative_sum = [0]
    i = 0
    for index, sv in enumerate(s):
        if index >= len(s)-1:
            continue
        if s[index] + s[index+1] == 'AC':
            i += 1
            cumulative_sum.append(i)
        else:
            cumulative_sum.append(i)
    for _ in range(q):
        l, r = input_list()
        if l == r-1:
            print(0)
            continue
        print(cumulative_sum[r-1] - cumulative_sum[l-1])


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: Wrong Answer

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

print(cumulative)    
    
for _ in range(Q):
  start, end = map(int, input().split())
  ans = cumulative[end] - cumulative[start-1]
  if start > 1 and S[start-2:start] == "AC":
    ans -= 1
  print(ans)

Submission status: Wrong Answer

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

for _ in range(Q):
  start, end = map(int, input().split())
  ans = cumulative[end] - cumulative[start-1]
  if start > 1 and S[start-2:start] == "AC":
    ans -= 1
  print(ans)

Submission status: Wrong Answer

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) #indexは０始まりだからー１
    r.append(r1 -1) #"AC"のAの位置と比べるため－２

# ACのindex(左端)
import re
import numpy as np
index =0
t =[0]*N

for i in range(N-1):
    t[i+1] = t[i] +np.count_nonzero(S[i:i+2] =="AC")

#
for i in range(Q):
    ans = t[ r[i]] - t[ l[i]] 
    print(ans)

print(t)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N, Q = map(int, input().split())
 
S = input()
 
ac = np.zeros(N-1)
 
for i in range(Q):
	l, r = map(int, input().split())
	print(S[l-1:r-1].count('AC'))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

S = input()

ac = np.zeros(N-1)

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

for i in range(q):
  b, c = list(map(int, input().split()))
  ans = a[c-1]-a[b-1]
  #if b != 1:
  #  if a[b-1] - a[b-2] == 1:
  #    if ans != 0:
  #      ans = ans - 1
  print(ans)

Submission status: Wrong Answer

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

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

for i in range(q):
  b, c = list(map(int, input().split()))
  ans = a[c-1]-a[b-1]
  if b != 1:
    if a[b-1] - a[b-2] == 1:
      if ans != 0:
        ans = ans - 1
  print(ans)

Submission status: Wrong Answer

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))
    for i in range(len(s)-1):
        if s[i]+s[i+1] == "AC":
            lst_ac[i+1] = lst_ac[i]+1
        else:
            lst_ac[i+1] = lst_ac[i]
    print(lst_ac)
    for item in l:
        print(lst_ac[item[1]-1] - lst_ac[item[0]-1])

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

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

a = [0] * N
c = [False] * N
for i in range(1, N):
    if S[i - 1:i + 1] == "AC":
        a[i] = a[i - 1] + 1
        a[i] = True
    else:
        a[i] = a[i - 1]

for i in range(Q):
    l, r = map(int, input().split())
    if l - 1 == 0:
        print(a[r - 1])
    elif c[l - 1] is True:
        print(a[r - 1] - a[l - 1] - 1)
    else:
        print(a[r - 1] - a[l - 1])

Submission status: Wrong Answer

Solution code:
def solve():
    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)
      
    print(t)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(t[r-1]-t[l-1])
        
solve()

Submission status: Wrong Answer

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

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

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

    ans = 0
    for j in range(len(pos)):
        if l <= pos[j] <= r - 1:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = str(input())
l = [-1] * q
r = [-1] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())
sum = [0] * (n+1)
flag_a = False
for i in range(1, n+1):
    if s[i-1] == 'A':
        flag_a = True
        sum[i] = sum[i-1]
    elif s[i-1] == 'C' and flag_a:
        flag_a = False
        sum[i] = sum[i-1] + 1
    else:
        flag_a = False
        sum[i] = sum[i-1]
print(sum)
for i in range(q):
    print(sum[r[i]] - sum[l[i]])

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,q = MI()
S = S()
lr = LI(q)

ls = [0]*n
count = 0
for i in range(1,n):
    if S[i]!="C":
        ls[i] = count
    else:
        if S[i-1]=="A":
            count += 1
            ls[i] = count
# print(ls)

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

Submission status: Wrong Answer

Solution code:
import itertools
import math
import fractions
import functools
import copy
n, q = map(int, input().split())
s = input()
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    li -= 1
    ri -= 1
    l.append(li)
    r.append(ri)

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



count = 0
print(count_list)

for i in range(q):
    print(count_list[r[i]]-count_list[l[i]])

Submission status: Wrong Answer

Solution code:
import itertools
import math
import fractions
import functools
import copy
n, q = map(int, input().split())
s = input()
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    li -= 1
    l.append(li)
    r.append(ri)

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

count = 0
print(count_list)
for i in range(q):
    if count_list[i] == 0:
        print(sum(count_list[l[i]:r[i]]))
    else:
        print(sum(count_list[l[i]:r[i]])-1)

Submission status: Wrong Answer

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

S = "AC"*(10**5//2)
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: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
lis=[]
for i in range(q):
    lis.append(list(map(int, input().split())))
idx=0
acs=[0]*n
for _ in s:
    if s[idx]=="A" and s[idx+1]=="C":
        acs[idx+1] = 1
        idx+=1
    idx+=1
    if idx>=(len(s)-1):
        break
cnt=0
print(acs)
for i,el in enumerate(acs):
    if el!=0:
        cnt+=el
        acs[i]=cnt
    else:
        acs[i]=cnt
print(acs)
for i in lis:
    print(acs[i[1]-1]-acs[i[0]-1])

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
lis=[]
for i in range(q):
    lis.append(list(map(int, input().split())))
idx=0
acs=[0]*n
for _ in s:
    if s[idx]=="A" and s[idx+1]=="C":
        acs[idx+1] = 1
        idx+=1
    idx+=1
    if idx>=(len(s)-2):
        break
cnt=0
#print(acs)
for i,el in enumerate(acs):
    if el!=0:
        cnt+=el
        acs[i]=cnt
    else:
        acs[i]=cnt
#print(acs)
for i in lis:
    print(acs[i[1]-1]-acs[i[0]-1])

Submission status: Wrong Answer

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #n = int(stdin.readline().rstrip())
    #l = list(map(int, stdin.readline().rstrip().split()))
    n,q = map(int, stdin.readline().rstrip().split())
    s = str(stdin.readline().rstrip())
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    cum = [0]*(n)
    cum[0] = 0
    for i in range(1,n):
        if s[i-1:i+1] == "AC":
            cum[i] = cum[i-1] + 1
        else:
            cum[i] = cum[i-1]
    print(cum)
    for i in range(q):
        l,r = map(int, stdin.readline().rstrip().split())
        print(cum[r-1] - cum[l-1])

main()

Submission status: Wrong Answer

Solution code:
import bisect

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

AC_l_list = []
AC_r_list = []

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        AC_l_list.append(i)
        AC_r_list.append(i + 1)
        
for l, r in lr_list:
    i = bisect.bisect_right(AC_l_list, l)
    j = bisect.bisect_left(AC_r_list, r)
    print(j - i + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def main():
    N, Q = map(int, input().split())
    S = input()
    appear = [0] * N # appear[i] = (0からi文字目までにACの出現した回数)

    prev = False
    if S[0] == 'A': prev = True
    for i in range(1, N):
        c = S[i]
        if c == 'A':
            prev = True
            appear[i] = appear[i - 1]
        elif prev and c == 'C':
            prev = False
            appear[i] = appear[i - 1] + 1
        elif prev:
            prev = False
            appear[i] = appear[i - 1]
        else:
            appear[i] = appear[i - 1]
    #print(appear)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        if S[l-1:l+1] == "AC":
            print(max(0, appear[r] - appear[l] - 1))
        else:
            print(appear[r] - appear[l])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def main():
    N, Q = map(int, input().split())
    S = input()
    appear = [0] * N # appear[i] = (0からi文字目までにACの出現した回数)

    prev = False
    if S[0] == 'A': prev = True
    for i in range(1, N):
        c = S[i]
        if c == 'A':
            prev = True
            appear[i] = appear[i - 1]
        elif prev and c == 'C':
            prev = False
            appear[i] = appear[i - 1] + 1
        else:
            appear[i] = appear[i - 1]
    #print(appear)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        if S[l-1:l+1] == "AC":
            print(max(0, appear[r] - appear[l] - 1))
        else:
            print(appear[r] - appear[l])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
ac = [0] * n
c = 1
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        ac[i] = c
        c += 1
for i in range(q):
    l, r = map(int, input().split())
    s, f = 0, 0
    for j in range(l - 1, r - 1):
        if ac[j] != 0:
            s = ac[j]
            break
    j = r - 2
    while j >= l:
        if ac[j] != 0:
            f = ac[j]
            break
        j -= 1
    print(f - s + 1)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
S=str(input())
AC_list=[0]*N
t=0
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    t+=1
  AC_list[i]=t
print(AC_list)
for i in range(Q):
  l,r=map(int,input().split())
  print(AC_list[r-1]-AC_list[l-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]
dp = [0] * (N)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i]

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

Submission status: Wrong Answer

Solution code:
l = [int(x) for x in input().split(" ")]
N,Q = l[0],l[1]
cumsum = [0]
string = input()
flag = False
for i in range(N):
  if not (string[i]=="A" or string[i]=="C"):
    flag = False
  elif string[i] == "A":
    flag = True
  elif string[i] == "C":
    if flag == True:
      cumsum.append(cumsum[-1]+1)
      continue
  cumsum.append(cumsum[-1])
for i in range(Q):
  t = [int(x) for x in input().split(" ")]
  print(cumsum[t[1]]-cumsum[t[0]])

Submission status: Wrong Answer

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

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

for l,r in Query:
    print(s[r-1]-s[l-1])

Submission status: Wrong Answer

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: Wrong Answer

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]=="C"):
        if (s[i-1]=="A"):
            a[i] += 1
print(a)
for i in range(q):
    l,r = map(int, input().split())
    print(a[r-1]-a[l-1])

Submission status: Wrong Answer

Solution code:
import math

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

S = list(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

    
#print(S)
def create_list():
  MAXI = N
  
  #ac = [1 for _ in range(MAXI+1)]
  

  sn = [0 for _ in range(MAXI+1)]
  flag = 0
  judge = ['A','C']
  for i in range(1,MAXI+1):
    #print(str(i)+'+1 when '+S[i-1])
    if(S[i-1] == judge[flag]):
        flag+=1
        if(flag == 2):
            sn[i] = sn[i-1] + 1
            flag = 0
        else:
            sn[i] = sn[i-1]
    else:
        flag = 0
        sn[i] = sn[i-1]
     
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]] )#sum(rnum)-sum(lnum) )

Submission status: Wrong Answer

Solution code:
import math

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

S = list(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

    
#print(S)
def create_list():
  MAXI = N
  
  #ac = [1 for _ in range(MAXI+1)]
  

  sn = [0 for _ in range(MAXI+2)]
  flag = 0
  judge = ['A','C']
  for i in range(1,MAXI+1):
    #print(str(i)+'+1 when '+S[i-1])
    if(S[i-1] == judge[flag]):
        flag+=1
        if(flag == 2):
            sn[i] = sn[i-1] + 1
            flag = 0
        else:
            sn[i] = sn[i-1]
    else:
        flag = 0
        sn[i] = sn[i-1]
     
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]] )#sum(rnum)-sum(lnum) )

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
S = input()
for _ in range(q):
  l,r = map(int,input().split())
  A = S[l:r+1]
  cnt = A.count('AC')
  print(cnt)

Submission status: Wrong Answer

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

A=[0]*(N)

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

print(A)

for k in li:
    l=k[0]-1
    r=k[1]-1
    print(A[r]-A[l])

Submission status: Wrong Answer

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":
        c=1
    else:
        c=0

    t[i+1]=t[i]+c

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,q=list(map(int,input().split()))
s=list(input())
l=[0]*q
r=[0]*q
for i in range(q):
  l[i],r[i]=list(map(int,input().split()))
A=[]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    A.append(1)
  else:
    A.append(0)
check=[0]+A+[0]
check=list(accumulate(check))
for i in range(q):
  print(check[r[i]-1]-check[l[i]])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def get_ac(n, q, s, lrli):
 
    ans = []
    for i in lrli:
        ans.append(s[i[0]-1:i[1]].count("AC"))
 
    return ans
 
def main():
    n, q = map(int, input().split())
    s = str(input())
    lrli = [list(map(int, input().split()))for i in range(q)]
    ans = get_ac(n, q, s, lrli)
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
cum = [0] * n  # i文字目までに含まれるACの個数
for i in range(1, n):
    if s[i-1:i+1] == 'AC':
        cum[i] = cum[i-1] + 1
    else:
        cum[i] = cum[i-1]
print(cum)

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