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:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    # ACがある場所を記録する
    buf = None
    mem = []
    tot = 0
    for i, c in enumerate(S):
        if buf is None and c == 'A':
            buf = 'A'
        elif buf == 'A' and c == 'C':
            tot += 1
            buf = None
        elif buf == 'A':
            buf = None
        mem.append(tot)
    # print(mem)
    for i in range(Q):
        if r[i]-l[i] < 1:
            print(0)
        else:
            print(mem[r[i]-1]-mem[l[i]-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    b = S()
    b = b[0]
    if b == "A":
        print("T")
    elif b == "T":
        print("A")
    elif b == "C":
        print("G")
    elif b == "G":
        print("C")
    return

#B
def B():
    s = S()
    agct = ["A", "G", "C", "T"]
    ans = 0
    for num, i in enumerate(s):
        ansb = 0
        if i in agct:
            ansb += 1
            for k in range(num+1, len(s)):
                if s[k] in agct:
                    ansb += 1
                else:
                    break
        ans = max(ans, ansb)
    print(ans)
    return

#C
def C():
    n, q = LI()
    s = S()
    s = s[::-1]
    ans = [0 for i in range(n)]
    ac = 0
    for num, ss in enumerate(s):
        if not ac and ss == "C":
            ac = 1
            ans[num] = ans[num-1]
        elif ac and ss == "A":
            ac = 0
            ans[num] += ans[num - 1] + 1
        else:
            ac = 0
            ans[num] = ans[num - 1]
    ans = ans[::-1]
    lr = LIR_(q)
    for l,r in lr:
        print(ans[l]-ans[r])

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Wrong Answer

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

Accumulation = [0]*N
flag = False

if (S[0] == "A"):
    flag = True

for i in range(1,N):
    if (flag):
        if (S[i] == "C"):
            Accumulation[i] = Accumulation[i-1] + 1
            flag = False
            continue
        else:
            flag = False
            Accumulation[i] = Accumulation[i-1]
            continue
    elif (S[i] == "A"):
        flag = True
    Accumulation[i] = Accumulation[i-1]

for eachRange in rangeList:
    print(Accumulation[eachRange[1]-1] - Accumulation[eachRange[0]-1])

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
e = [[int(i) for i in input().split()] for i in range(q)]
for m in range(q):
  lim = s[e[m][0]:e[m][1]]
  print(lim.count("AC"))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import itertools
import re
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        cnt = 0
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        """
        for i in range(R-L):
            #print(i)
            cnt += cntAC(R-i-1, R-i, S)
        print(cnt)
        """
    return
 

def cntAC(l, r, S):
    global dp
    global T
    if l+r not in T:
        T[l+r] = S[l-1:r]
        t = T[l+r]
        print(t)
    if l+r not in dp:
        if t == 'AC':
            dp[l+r] = 1
        else:
            dp[l+r] = 0
    return dp[l+r]
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Accumulation = [0]*N
flag = False

if (S[0] == "A"):
    flag = True

for i in range(1,N):
    if (flag):
        if (S[i] == "C"):
            Accumulation[i] = Accumulation[i-1] + 1
            flag = False
            continue
        else:
            flag = False
            Accumulation[i] = Accumulation[i-1]
            continue
    elif (S[i] == "A"):
        flag = True
    Accumulation[i] = Accumulation[i-1]

print(Accumulation)
for eachRange in rangeList:
    print(Accumulation[eachRange[1]-1] - Accumulation[eachRange[0]-1])

Submission status: Wrong Answer

Solution code:
import re

N, S = map(int, input().split(' '))
pattern = "AC+"
T = input()
for _ in range(S):
    first,final = map(int, input().split(' '))
    print(first, final)
    result = re.findall(pattern, T[first -1:final])
    print(result)
    print(len(result))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    # ACがある場所を記録する
    buf = None
    mem = []
    tot = 0
    for i, c in enumerate(S):
        if buf is None and c == 'A':
            buf = 'A'
        elif buf == 'A' and c == 'C':
            tot += 1
            buf = None
        elif buf == 'A':
            buf = None
        mem.append(tot)
    # print(mem)
    for i in range(Q):
        if r[i]-l[i] < 2:
            print(0)
        else:
            print(mem[r[i]-1]-mem[l[i]-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,q =map(int,input().split())
s=input()
l=[input() for i in range(q)]
for j in range(q):
    a=int(l[j][0])-1
    b=int(l[j][-1])
    c=s[a:b]
    cnt=0
    for k in range(len(c)-1):
        if c[k]+c[k+1]=='AC':
            cnt+=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
s = str(input())
for i in range(0, Q):
  l, r = map(int, input().split())
  print(s.count('AC'))

Submission status: Wrong Answer

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

Accumulation = [0]*N
flag = False

if (S[0] == "A"):
    flag = True

for i in range(1,N):
    if (flag):
        if (S[i] == "C"):
            Accumulation[i] = Accumulation[i-1] + 1
            continue
        else:
            flag = False
            Accumulation[i] = Accumulation[i-1]
            continue
    elif (S[i] == "A"):
        flag = True
    Accumulation[i] = Accumulation[i-1]

for eachRange in rangeList:
    print(Accumulation[eachRange[1]-1] - Accumulation[eachRange[0]-1])

Submission status: Wrong Answer

Solution code:
n,q = (int(i) for i in input().split())  
s = input()
for i in range(q):
    cnt = 0
    li,ri = (int(x) for x in input().split())
    length = ri-li
    for p in range(li-1,ri-1):
        print(p,s[p:p+2])
        if s[p:p+2] == "AC":
            cnt+=1
            p+=2
    print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

ss = ""
a = [0] * n
b = [0] * n
for i in range(n):
    if s[i] == "A":
        ss = s[i]
    elif s[i] == "C":
        ss += s[i]
    if ss == "AC":
        a[i] = a[i - 1] - 1
        b[i] += b[i - 1] + 1
        ss = ""
    else:
        if i > 0:
            a[i] = a[i - 1]
            b[i] = b[i - 1]

for i in range(q):
    x, y = map(int, input().split())
    print(max(0, b[y - 1] + a[x - 1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

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

ss = S.split('AC')
a = []
q = 0
for s in ss:
    q += len(s)
    a.append(q)
    q += 2
a = a[:-1]
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:
    print(0)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]
flag = False
q_flag = []
count = 0
for x in S:
    count += 1
    if x == 'A':
        flag = True
    elif x == 'C' and flag == True:
        flag = False
        q_flag.append(count)
    else:
        flag = False
print(q_flag)
for y in lr:
    ans = len([_1 for _1 in q_flag if y[0]<_1 and _1<=y[1]])
    print(ans)

Submission status: Wrong Answer

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

T = list(S)
hoge = ""
cnt = 0

for i in range(Q):
    for j in range(lr[i][1] - lr[i][0]):
        hoge += S[j]
    for k in range(len(list(hoge)) - 1):
        if hoge[k] == "A" and hoge[k + 1] == "C":
            cnt += 1
    print(hoge)
    print(cnt)
    hoge = ""
    cnt =0

print(lr)

Submission status: Wrong Answer

Solution code:
nq = list(map(int, input().split()))
n = nq[0]
q = nq[1]
s = input()
ac = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ac.append(i)
print(ac)
for i in range(q):
    lr = list(map(int, input().split()))
    l = lr[0]
    r = lr[1]
    ans = 0
    for j in ac:
        if l - 1 <= j < r - 1:
            ans += 1
        elif j >= r - 1:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import re

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())]
    l.append(l_i)
    r.append(r_i)

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

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1
    out_list.append(str(sum(p_list[l_i:r_i])))

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

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
positions = []
i = 0
while i < n-1:
	if s[i]+s[i+1]=="AC":
		positions.append(i+1)
		i += 1
	i += 1

length = len(positions)

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

	left = 0
	right = length-1
	while left < right:
		current = positions[left]
		if current >= l:
			break
		else:
			left += 1
	while right > left:
		current = positions[right]
		if current < r:
			break
		else:
			right -= 1

	if right == left:
		if positions[right]<r:
			print(1)
		else:
			print(0)
	else:
		print(right-left+1)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
ans = []
for i in range(Q):
    z,x = map(int,input().split())
    ans.append(S[z:x].count('AC'))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
positions = []
i = 0
while i < n-1:
	if s[i]+s[i+1]=="AC":
		positions.append(i+1)
		i += 1
	i += 1

length = len(positions)
print(positions)

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

	left = 0
	right = length-1
	while left < right:
		current = positions[left]
		if current >= l:
			break
		else:
			left += 1
	while right > left:
		current = positions[right]
		if current < r:
			break
		else:
			right -= 1

	if right == left:
		if positions[right]<r:
			print(1)
		else:
			print(0)
	else:
		print(right-left+1)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = input()
inputl = []
inputr = []
for i in range(0,Q):
    l,r = map(int, input().split())
    inputl.append(l)
    inputr.append(r)
answerlist = []
for j in range(0,Q):
    l = inputl[j]
    r = inputr[j]
    appear = 0
    k = 0
    while(l+k+1<r):
    #for k in range(0,N):
        if(S[l+k-1:l+2+k-1] == 'AC'):
            appear = appear +1
        k = k+1
    answerlist.append(appear)
for p in range(0,Q):
    print(answerlist[p])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,Q = map(int,input().split())
S = input()
p = set()
for n,i in enumerate(S[:-1]):
    if i == "A" and S[n+1]=="C":
        p.add(n)
#print(p)
for i in range(Q):
    a,b = map(int,input().split())
    #tmp = {}
    # tmp = {i for i in range(a-1,b-1)}
    # print(tmp)
    # print(len(tmp&p))
    count=0
    for j in p:
        #print("j",j)
        if a <= j+1 and j+1 < b:
            count+=1
        elif j > b:
            break
    print(count)

Submission status: Wrong Answer

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

S = input()
ans = []

for i in range(len(S)):
    if S[i:i + 2] == 'AC':
        ans.append(i)


for i in range(Q):
    l, r = map(int, input().strip().split())
    ret = 0
    ali, ari = 0, 0
    for a in ans:
        if l - 1 <= a and a < r and S[l-1] != 'C':
           ret += 1
    print(ret)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = input()
x = [0]
flag = False
for i in range(len(s)):
    if s[i] == 'A' and flag==False:
        flag=True
        x.append(x[i])
    elif s[i]=='C' and flag:
        flag = False
        x.append(x[i]+1)
    else:
        flag = False
        x.append(x[i])

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

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    start = s[l-1:r].find('A')
    end = s[l-1:r].rfind("C")
    if start == -1 or end== -1 or end <= start:
        print(0)
        pass
    cand = s[l-1:r][start:end+1]
    print(cand.count("AC"))

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
flag = 0
max = S.count('AC')
if max == 0:
    for i in range(Q):
        print(0)
for i in range(Q):
    L,R = map(int,input().split())
    if R - L + 1 == N:
        print(max)
    else:
        print(S[L-1:R].count('AC'))

Submission status: Wrong Answer

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

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

anss = [[-1] * (n+1)]*(n+1)
for item in lr:
  if anss[item[0]][item[1]] != -1:
    print(anss[item[0]][item[1]])
    continue
  ans = sum(is_ac[item[0]-1: item[1]])
  if s[item[1]-1] == "A":
    if item[1] != n:
      if s[item[1]] == "C":
        ans -= 1
  anss[item[0]][item[1]] = ans
  print(ans)

Submission status: Wrong Answer

Solution code:
N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
indexlist = []
for i in range(len(S)-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            indexlist.append(i)
for LR in LRlist:
    L = LR[0]
    R = LR[1]
    answer = 0
    for i in indexlist:
        if L - 1 <= i <= R - 2:
            answer += 1
        elif i < L - 1:
            break
    print(answer)

Submission status: Wrong Answer

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

dp = [0] * len(S)
flag = 0
for i in range(N):
    if flag == 1 and S[i] == 'C':
        dp[i] += 1
        flag = 0
    elif flag == 0 and S[i] == 'A':
        flag = 1
    else:
        flag = 0
        
for i in range(1, N):
    dp[i] += dp[i - 1]
        
for i in range(Q):
    l, r = map(int, input().split())
    print(dp[r - 1] - dp[l - 1])

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    start = s[l-1:r].find('A')
    end = s[l-1:r].rfind("C")
    if start == -1 or end== -1:
        print(0)
        pass
    cand = s[l-1:r][start:end+1]
    print(cand.count("AC"))

Submission status: Wrong Answer

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

flag = 0
li = []
for i in range(N):
    if S[i] == 'A':
        flag = 1
    if S[i] == 'C' and flag == 1:
        li.append(i)

ans = []
for _ in range(Q):
    a,b = [int(i) for i in input().split()]
    p = -1
    q = -1
    p_flag = 0
    q_flag = 0
    for j in range(len(li)):
        if a <= li[j] and p_flag == 0:
            p = j
            p_flag = 1
        if b <= li[j] and q_flag == 0:
            q = j
            q_flag = 1
    if q == -1:
        q = len(li)
    ans.append(q-p)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import re

n, q = map(int, input().split())
s = input()
positions = []
for i in range(n-1):
	if s[i]+s[i+1]=="AC":
		positions.append(i+1)

length = len(positions)

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

	left = 0
	right = length-1
	while left < right:
		current = positions[left]
		if current >= l:
			break
		else:
			left += 1
	while right > left:
		current = positions[right]
		if current < r:
			break
		else:
			right -= 1

	if right == left:
		if positions[right]<r:
			print(1)
		else:
			print(0)
	else:
		print(right - left+1)

Submission status: Wrong Answer

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

N, M = (int(i) for i in input().split())
moji = input()
e = [[int(i) for i in input().split()] for i in range(M)]

c_list = []

if moji.count('AC'):
    print(0)
    exit()

for idx in e:
    sub = moji[idx[0]-1:idx[1]]
    if 'AC' in sub:
        print(sub.count('AC'))
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
lr_list = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

#result_list = []
count = 0

result_list = deque([])

for i in range(N):
    result_list.append(count)
    if S[i] != "A":
        continue
    try:
        if S[i+1] == "C":
            count += 1
    except:
       pass
print(result_list)

for l, r in lr_list:
    print(result_list[r-1] - result_list[l-1])

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

ss = ""
if s[0] == "A":
    ss = "A"
a = [0] * n
b = [0] * n
for i in range(1, n):
    if s[i] == "A":
        ss += s[i]
    elif s[i] == "C":
        ss += s[i]
    else:
        ss = ""
    if ss == "AC":
        a[i] = a[i - 1] - 1
        b[i] += b[i - 1] + 1
        ss = ""
    else:
        a[i] = a[i - 1]
        b[i] = b[i - 1]

for i in range(q):
    x, y = map(int, input().split())
    print(max(0, b[y - 1] + a[x - 1]))

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = input()
x = [0  for i in range(n+1)]
flag = False
for i in range(len(s)):
    if s[i] == 'A' and flag==False:
        flag=True
        x[i+1] = x[i]
    elif s[i]=='C' and flag:
        flag = False
        x[i+1] = x[i]+1
    else:
        flag = False
        x[i+1] = x[i]

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

Submission status: Wrong Answer

Solution code:
N, Q = (int(x) for x in input().split())
S = input()
lr = [[0 for i in range(2)] for j in range(Q)]
ans = []
loffset = 0
rlimit = -1
for i in range(len(S)):
    if S[i:i+2] == 'AC':
        loffset = i
        break
for i in range(len(S)-1, loffset+1, -1):
    if S[i:i+2] == 'AC':
        rlimit = i + 1
        break
    
for i in range(Q):
    l, r = (int(x) for x in input().split())
    l -= 1
    r -= 1
    num = 0
    if l < loffset:
        l = loffset
    if r > rlimit:
        r = rlimit
    for j in range(l, r):
        if S[j:j+2] == 'AC':
            num += 1
    ans.append(num)

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N,Q=list(map(int,input().split()))
S=input()
place=[0]*(N+1)
for i in range(0,len(S)-1):
    if S[i:i+2]=='AC':
        place[i+2]+=1
        
for i in range(N):
    place[i+1]=place[i]+place[i+1]
for i in range(Q):
    frm,to=list(map(int,input().split()))
    print(place[to]-place[frm-1])

Submission status: Wrong Answer

Solution code:
N,Q=list(map(int,input().split()))
S=input()
place=[0]*(N+1)
for i in range(0,len(S)-1):
    if S[i:i+2]=='AC':
        place[i+2]+=1
        
for i in range(N):
    place[i+1]=place[i]+place[i+1]
for i in range(Q):
    frm,to=list(map(int,input().split()))
    print(place[to]-place[frm-1])
print(place)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
raw_list = list(input())
def count_ac(l,r):
    cnt = 0
    sliced_list = raw_list[l-1:r+1]
    for idx,char in enumerate(sliced_list):
        if idx == len(sliced_list)-1:
            break
        if sliced_list[idx] == "A":
            if sliced_list[idx+1] =="C":
                cnt += 1

    print(cnt)

for i in range(q):
    li, ri = map(int,input().split())
    count_ac(li, ri)

Submission status: Wrong Answer

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

start_pair = [-1]
for j in range(N-1):
    if S[j] == 'A' and S[j+1] == 'C':
        start_pair.append(j)

length = len(start_pair)
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    Count = 0
    left = 0
    right = length-1
    while left < length:
        if l > start_pair[left]:
            left += 1
        else:
            left -= 1
            break
    while right >= 0:
        if r <= start_pair[right]:
            right -= 1
        else:
            break
    print(right-left)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [[int(x) for x in input().split()] for i in range(Q)]
zz = S.count('AC')
for i in range(Q):
  l = lr[i][0]
  r = lr[i][1]
  z = r-l
  if z < N-z:
    tmp = S[l-1:r]
    print(tmp.count('AC'))
  else:
    tmp1 = S[:l-1]
    tmp2 = S[r:]
    print(zz-tmp1.count('AC')-tmp2.count('AC'))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
index = []
for i in range(len(s)):
    if s[i:i+2] == "AC":
        index.append(i)
for i in range(q):
    l, r = na()
    print(len([i for i in index if l-1<= i <= r-1]))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import re

N,Q = map(int, input().split())
S = input()
S_len = len(S)
S_count = S.count('AC')
ans = str()
for _ in range(Q):
    l,r = map(int, input().split())
    if r-l < S_len/2:
        s = S[l-1:r]
        ans = s.count('AC')
    else:
        s_l = S[0:l-1]
        s_r = S[r:]
        ans = S_count - s_l.count('AC') - s_r.count('AC')
    print(ans)

Submission status: Wrong Answer

Solution code:
n,q =map(int,input().split())
s=input()
l=[input() for i in range(q)]
for j in range(q):
    cnt=0
    a=int(l[j][0])-1
    b=int(l[j][-1])-1
    for k in range(b-a):
        if s[a+k]+s[a+k+1]=='AC':
            cnt+=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N, Q= input().split(" ")
S = input()
index_list = []
index_list_all = []
for i in range(int(Q)):
    lQ, rQ = input().split(" ")
    index_list_all.append(index_list)
print(len(Q[1 - 1: 8].split("AC")) - 1)

Submission status: Wrong Answer

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

import re
ptn = re.compile(r"(AC)*")

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

Submission status: Wrong Answer

Solution code:
import bisect
N,Q=[int(i) for i in input().split()]
S=input()
AC=list()
for i in range(len(S)-1):
    if S[i]=='A' and S[i+1]=='C':
        AC.append(i)
print(AC)
for i in range(Q):
    L,R=[int(i)-1 for i in input().split()]
    R-=1
    ll=bisect.bisect_left(AC,L)
    rr=bisect.bisect_right(AC,R)
    print(rr,ll,rr-ll)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [[int(x) for x in input().split()] for i in range(Q)]
zz = S.count('AC')
for i in range(Q):
  l = lr[i][0]
  r = lr[i][1]
  z = r-l
  if z < N-z:
    tmp = S[l-1:r]
    print(tmp.count('AC'))
  else:
    tmp1 = S[:l-2]
    tmp2 = S[r:]
    print(zz-tmp1.count('AC')+tmp2.count('AC'))

Submission status: Wrong Answer

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

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

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


if __name__ == '__main__':
    C()

Submission status: Wrong Answer

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

ans_list = []
fa = 0
ans = 0
for index, s in enumerate(S):
    if s == 'A' and fa == 0:
        fa = 1
        ans_list.append(ans)
    elif s == 'A' and fa == 1:
        ans_list.append(ans)
    elif s == 'C' and fa == 1:
        fa = 0
        ans += 1
        ans_list.append(ans)
    else:
        fa = 0
        ans_list.append(ans)
print(ans_list)
for _ in range(Q):
    l, r = map(int, input().split())
    print(ans_list[r-1] - ans_list[l-1])

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)]
bef = ''
pos = []
for idx,val in enumerate(S):
    if val == 'C' and bef == 'A':
        pos.append((idx -1) * 10 + idx)
    bef = val

cnt = 0
for i in range(Q):
    min_v = (lr[i][0] - 1) * 10 + lr[i][0]
    max_v = (lr[i][1] - 2) * 10 + (lr[i][1] - 1)
    init_pos = 0
    last_pos = 0
    for idx,p in enumerate(pos):
        if p >= min_v:
            init_pos = idx
            break
        elif p > max_v:
            break
    for idx,p in enumerate(reversed(pos)):
        if p <= max_v:
            last_pos = len(pos) - idx - 1
            break
        elif p < min_v:
            break
    print(last_pos - init_pos + 1) if last_pos != 0 or init_pos != 0 else print(0)

Submission status: Wrong Answer

Solution code:
import bisect
N,Q=list(map(int,input().split()))
S=input()
place=[]
for i in range(0,len(S)-1):
    print(S[i:i+2])
    if S[i:i+2]=='AC':
        place.append(i+2)

for i in range(Q):
    frm,to=list(map(int,input().split()))
    if to-frm<=1:
        print(0)
    else:
        f=bisect.bisect_left(place,frm-1)
        t=bisect.bisect_left(place,to)
        print(t-f)

#print(place)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [[int(x) for x in input().split()] for i in range(Q)]
zz = S.count('AC')
for i in range(Q):
  l = lr[i][0]
  r = lr[i][1]
  z = r-l
  if z < N-z:
    tmp = S[l-1:r]
    print(tmp.count('AC'))
  else:
    tmp1 = S[:l]
    tmp2 = S[r-1:]
    print(zz-tmp1.count('AC')+tmp2.count('AC'))