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

for lr_v in lr:
    k = 0
    for i in range(lr_v[0] - 1, lr_v[1] + 1, 2):
        if s[i:i + 2] == "AC":
            k += 1

        if i + 2 < lr_v[1]:
            if s[i + 1:i + 3] == "AC":
                k += 1

    print(k)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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

i = 0
ac_indices = []
while True:
    index = S[i:].find('AC')
  
    if index == -1:
        break
    else:
        ac_indices.append(i + index)
        i +=  index + 1

for _ in range(Q):
    start, end = map(int, input().rstrip().split(' '))
    start -= 1
    end -= 1
    
    start_index = 0
    for i, ac_index in enumerate(ac_indices):
        if ac_index >= start:
            start_index = i
            break
        
    end_index = len(ac_indices)
    count = 0
    for i, ac_index in enumerate(ac_indices[start_index:]):
        if (ac_index + 1) > end:
            end_index = i + start_index
            break
        count += 1
        
    print(end_index - start_index)

Submission status: Wrong Answer

Solution code:
import sys

l = raw_input().split()
N = int(l[0])
Q = int(l[1])
l = raw_input().split()
S = l[0]

L = [0]*Q
R = [0]*Q

ac = 'AC'

for i in range(Q):
    l = raw_input().split()
    L[i] = int(l[0])
    R[i] = int(l[1])

#print(N,Q,S,L,R)

def count(S, table):
    length = len(S)
    c = 0
    for i in range(length - 1):
        # print(S[i:i+2])
        if ac == S[i:i+2]:
            c += 1
        table[i+1] = c

length_S = len(S)
table = [0]*length_S

count(S, table)
print(table)

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

Submission status: Wrong Answer

Solution code:
def countAC(s):
    index = []
    for i in range(len(s)):
        if i == len(s)-1:
            break
        if s[i] == 'A':
            if s[i+1] == 'C':
                index.append(1)
                continue
        index.append(0)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    s = SIndex[l-1:r]
    for x in range(len(s)):
        out += x
    print(out)
    out = 0

Submission status: Wrong Answer

Solution code:
import re
N, Q = map(int, input().split())
S = input()
indices = [(m.start(0), m.end(0)) for m in re.finditer("AC", S)]
print(indices)
for _ in range(Q):
    li, ri = map(int, input().split())
    print(len([x for x in indices if x[0] >= li - 1 and x[0] <= ri - 1]))

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):
        tot = 0
        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=str(input())
data=[]
for i in range(Q):
    data.append([int(j) for j in input().split()])
import re
ans=[]
for i in range(Q):
    ans.append(len(re.findall('AC',S[data[i][0]-1:data[i][1]])))
print(ans[:])

Submission status: Wrong Answer

Solution code:
import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 2
    bl = bisect.bisect_left(index, l)
    br = bisect.bisect_left(index, r)
    if bl == br:
        print(0)
    elif br - bl >= len(index):
        print(len(index))
    else:
        print(br - bl + 1)

Submission status: Wrong Answer

Solution code:
n,q = (int(i) for i in input().split())
s = input()
query = [0]*(n+1)
point = [0]*(n+1)
ct = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    ct += 1
  elif s[i] == 'C' and s[i+1] =='A':
    if i>0:
     if s[i-1] == 'A':
      point[i+1] -= 1
  query[i+1] = ct
query[i+2] = ct  
#print(query)
    
for i in range(q):
  l,r = (int(i) for i in input().split())
  ans = query[r]-query[l-1]
  ans += point[r-1]
  print(ans)

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

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

ans=[]
for i in range(Q):
    count=0
    for p in lst:
        if lr[i][0] <= p and p+1 <= lr[i][1]:
            count += 1
    ans.append(count)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import re
N,Q = input().split()
S = input()
for _ in range(int(Q)):
    l,r = input().split()
    print(len(re.findall(r'AC', S[int(l)-1:int(r)+1])))

Submission status: Wrong Answer

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

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

for _ in range(q):
  l,r=map(int,input().split())
  c=a[r-1]-a[l-1]
  print(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)]
print(lr)
for q in range(Q):
    q_lis = S[lr[q][0]-1:lr[q][1]]
    try:
        #print(q_lis)
        print(q_lis.count('AC'))
    except:
        print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,q = map(int, input().split())

# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(q)] 
c = [0]
# n番目までに何個ACがあるか


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

for i in range(q):
    if x[i][0] == 1:
        print(c[x[i][1]-1])
    else:
        print(c[x[i][1]-1]-c[x[i][0]-1])

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
s = input()
l = [[int(i) for i in input().split()] for i in range(q)]
c = [0 for i in range(n)]
cc = 0
f = False
for i in range(n):
    if f:
        if s[i] == "C":
            cc += 1
            f = False
        else:
            f = False
    if s[i] == "A":
        f = True
    c[i] = cc
print(c)
for i in range(q):
    print(c[l[i][1]-1]-c[l[i][0]-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = list(str(input()))
agct = {'A', 'C', 'G', 'T'}

ans_list = []
fa = 0
for index, s in enumerate(S):
    if s == 'A' and fa == 0:
        fa = 1
    elif s == 'C' and fa == 1:
        fa = 0
        ans_list.append(index+1)
    else:
        fa = 0

for _ in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for num in ans_list:
        if l < num <= r:
            ans += 1
        if num > r:
            break
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,q = (int(i) for i in input().split())
s = input()
query = [0]*(n+1)
point = [0]*(n+1)
ct = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    ct += 1
  elif s[i] == 'C' and s[i+1] =='A':
    point[i+1] -= 1
  query[i+1] = ct
query[i+2] = ct  
#print(query)
    
for i in range(q):
  l,r = (int(i) for i in input().split())
  ans = query[r]-query[l-1]
  ans += point[r-1]
  print(ans)

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())
    m=S[l-1:r]
    M=0
    count=0
    for s in m:
        if s in "A":count+=1
        elif s in "C":count+=1
        elif s in "G":count+=1
        elif s in "T":count+=1
        else:
            count=0
        M=max(M,count)
    print(M)

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):
    if S[i:i+2]=='AC':
        place.append(i)

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-1)
        print(t-f)

#print(place)

Submission status: Wrong Answer

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

AC = [0 for i in range(N)]
A = []


for k in range(N-1):
    if (S[k] in "A") and (S[k+1] in "C"):
        AC[k] = 1
print(AC)


for i in range(Q):
    score = sum(AC[l[i]-1:r[i]-1])
    A.append(score)

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

Submission status: Wrong Answer

Solution code:
#122-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,q=IL()
S=S()
J=[0]*n
A=[]
for i in range(1,n):
    if S[i]=="C" and S[i-1]=="A":
        J[i]=1
        A.append(i-1)
for i in range(n-1):
    J[i+1]+=J[i]
for i in range(q):
    l,r=IL()
    ans=J[r-1]-J[max(l-2,0)]
    if S[l-1]=="C":
        print(ans-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, q = LI()
    s = 'X' + SI()
    Q = [LI() for _ in range(q)]

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

    print(ac)
    for l, r in Q:
        print(ac[r] - ac[l])
    # return res


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, Q = map(int, raw_input().split())
S = raw_input()
cnt = [0] * (N + 1)
for i in range(N - 1):
    cnt[i + 2] = cnt[i + 1]
    if S[i] == 'A' and S[i + 1] == 'C':
        cnt[i + 2] += 1
print cnt
for _ in range(Q):
    l, r = map(int, raw_input().split())
    ans = cnt[r] - cnt[l - 1]
    if cnt[l] != cnt[l - 1]:
        ans -= 1
    print ans

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator
import re


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


# inputs
N, Q = 0, 0
S = ""
L, R = [], []


def set_inputs():
    global N, Q, S, L, R
    N, Q = get_li()
    S = get_str()
    L, R = get_data(Q, [int, int])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    a, c = [], []
    for m in re.finditer("AC", S):
        a.append(m.start())
        c.append(m.end())
    for l, r in zip(L, R):
        s = bisect_right(a, l-1)
        e = bisect_right(c, r)
        if e - s <= 0:
            print(0)
        else:
            print(e - s + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N, Q = map(int, input().split())
S = input()
l = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        l[i + 1] = 1
for _ in range(Q):
    ans = 0
    a, b = map(int, input().split())
    ans = sum(l[a - 1: b])
    if l[a - 1] == 1:
        ans -= 1
    print(ans, l)

Submission status: Wrong Answer

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

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

print(acs)
for i in range(Q):
	c=0
	for j in range(len(acs)):
		if l[i]-1 <= acs[j] and acs[j] < r[i]-1: c+=1
	print(c)

Submission status: Wrong Answer

Solution code:
import bisect

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

index_list = []
idx = 0
while idx < len(S):
    i2 = S.find("AC", idx)
    if i2 < 0:
        break
    index_list.append(i2)
    idx = i2 + 2

for q in Qi:
    if len(index_list) == 0:
        print(0)
        continue
    left = bisect.bisect_left(index_list, q[0] - 1)
    right = bisect.bisect_right(index_list, q[1] - 2)
    print(right - left, left, right)

Submission status: Wrong Answer

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

num_list = []
tochu = [0 for _ in range(N)]
tochu2 = [0 for _ in range(N)]

state = 0
count = 0
for t_i, t in enumerate(S): 
    if "A" == t:
        state = 1
    elif "C" == t and state == 1:
        tochu[t_i-1] = 1
        tochu2[t_i] = 1
        state = 0
        count += 1
    else:
        state = 0
    num_list.append(count)

#print(num_list, tochu)
outs = []
for Q_i in range(Q):
    l, r = list(map(int, input().split(" ")))
    l -= 1
    r -= 1
    out = max(0, num_list[r] - num_list[l] - tochu2[l])
    outs.append(out)

for out in outs:
    print(out)

Submission status: Wrong Answer

Solution code:
def main_(lst):
    a=s[lst[0]-1:lst[1]]
    return a.count("AC")

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

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]
    for _ in range(q):
        l, r = LI_()
        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:
#!/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
        mem.append(tot)
    for i in range(Q):
        tot = 0
        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 = list(map(int, input().split(" ")))
s = input()
l = q*[0]
r = q*[0]
for i in range(q):
    l[i], r[i] = list(map(int, input().split(" ")))


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

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

Submission status: Wrong Answer

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

countlist = [0 for i in range(N)]
for i in range(1, N):
    #print(S[i - 1:i + 1])
    countlist[i] = countlist[i - 1]
    if S[i - 1:i + 1] == ["A", "C"]:
        countlist[i] += 1

#print(countlist)
for i in range(Q):
    #print(i)
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = countlist[r] - countlist[l - 1]
    if S[r] == "C" and S[r - 1] == "A":
        ans -= 1
    if l == 0:
        ans = countlist[r]
    print(ans)
#print(countlist)

Submission status: Wrong Answer

Solution code:
#122-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,q=IL()
S=S()
J=[0]*n
A=[]
for i in range(1,n):
    if S[i]=="C" and S[i-1]=="A":
        J[i]=1
        A.append(i-1)
for i in range(n-1):
    J[i+1]+=J[i]
for i in range(q):
    l,r=IL()
    ans=J[r-1]-J[max(l-2,0)]
    print(ans)

Submission status: Wrong Answer

Solution code:
# 1からn文字目までの部分文字列にACがいくつ含まれるか？

def main():
    N, Q = [int(n) for n in input().split()]
    cnt = [0] * N
    S = input()
    ans = [0] * Q

    cnt[0] = 0
    is_prev_a = S[0] == "A"
    for index in range(1, N):
        char = S[index]
        if char == "A":
            is_prev_a = True
            cnt[index] = cnt[index - 1]
        elif is_prev_a and char == "C":
            is_prev_a = False
            cnt[index] = cnt[index - 1] +  1
        else:
            is_prev_a = False
            cnt[index] = cnt[index - 1]
    print(cnt)
    for q in range(Q):
        l, r = [int(n) for n in input().split()]
        ans[q] = (cnt[r - 1] - cnt[l - 1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

countlist = [0 for i in range(N)]
for i in range(1, N):
    #print(S[i - 1:i + 1])
    countlist[i] = countlist[i - 1]
    if S[i - 1:i + 1] == ["A", "C"]:
        countlist[i] += 1

#print(countlist)
for i in range(Q):
    #print(i)
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = countlist[r] - countlist[l - 1]
    if S[r] == "C":
        ans -= 1
    if l == 0:
        ans = countlist[r]
    print(ans)
#print(countlist)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    bl = bisect.bisect_right(index, l)
    br = bisect.bisect_right(index, r)
    if br - bl:
        print(br - bl + 1)
    else:
        print(0)

Submission status: Wrong Answer

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

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

S = input()

A = []
for i in range(Q):
    A.append([int(i) for i in input().split()])

print(S)

for x in A:
    # print(S[(x[0]-1):(x[1])])
    m = re.findall('AC', S[(x[0]-1):(x[1])])
    #print(m)
    print(len(m))

Submission status: Wrong Answer

Solution code:
N, Q =  map(int, (input().split(' ')))
S = str(input())
lr = [tuple(map(int, input().split(' '))) for _ in range(Q)]
save = [0] * N
print(N)
print(Q)
print(S)
i = 0
while i < len(S):
    if S[i] == "A":
        if S[i+1] == "C":
            save[i] = 1
        i += 2
    elif S[i] == "C":
        i += 1
    else:
        i+=1

for left, right in lr:
    print(sum(save[left-1: right-1]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
S=input()
query=[[int(i) for i in input().split()]for i in range(Q)]
L=[0]*(N+1)
t=0
for i in range(N):
    a=0
    if t==1 and S[i]=='C':
        a=1
        t=0
    elif S[i]=='A':
        t=1
    L[i+1]=L[i]+a
#print(L)
for a,b,in query:
    a,b=a-1,b-1
    t=L[b+1]-L[a]
    if a>=1 and S[a]=='C' and S[a-1]=='A':
        t-=1
    print(t)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

countlist = [0 for i in range(N)]
for i in range(1, N):
    #print(S[i - 1:i + 1])
    countlist[i] = countlist[i - 1]
    if S[i - 1:i + 1] == ["A", "C"]:
        countlist[i] += 1

#print(countlist)
for i in range(Q):
    #print(i)
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = countlist[r] - countlist[l - 1]
    if S[r] != "C":
        ans -= 1
    if l == 0:
        ans = countlist[r]
    print(ans)
#print(countlist)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = input()
wa = [0] * (N + 1)
flag = "X"
for i in range(N):
    if S[i] == "A":
        flag = "A"
        wa[i+1] = wa[i]
    elif flag == "A" and S[i] == "C":
        wa[i+1] = wa[i] + 1
        flag = "X"
    else:
        flag = "X"
        wa[i+1] = wa[i]

print(wa)
for q in range(Q):
    left,  right = map(int, input().split())
    print(wa[right] - wa[left])

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()
    ans = [0 for i in range(n)]
    ac = 0
    for num, ss in enumerate(s):
        if not ac and ss == "A":
            ac = 1
            ans[num] = ans[num-1]
        elif ac and ss == "C":
            ac = 0
            ans[num] += ans[num - 1] + 1
        else:
            ac = 0
            ans[num] = ans[num-1]
    for _ in range(q):
        l, r = LI_()
        print(ans[r]-ans[l])


    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:
import bisect
N, Q = [int(x) for x in input().split()]
S = str(input())

ac_list = []
for (idx, (s1, s2)) in enumerate(zip(S[:-1], S[1:])):
  if s1 == 'A' and s2 == 'C':
    ac_list.append(idx+1)

print(ac_list)
for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  index_l = bisect.bisect_left(ac_list, l)
  index_r = bisect.bisect_left(ac_list, r)
  print(index_r - index_l)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, q = LI()
    s = SI() + 'X'
    Q = [LI() for _ in range(q)]

    ac = [0]
    for i, ss in enumerate(zip(s[:-1], s[1:])):
        if ss == ('A', 'C'):
            ac.append(ac[-1] + 1)
        else:
            ac.append(ac[-1])

    for l, r in Q:
        res = ac[r] - ac[l] + 1

        if ac[l] != ac[l + 1]:
            res -= 1
        if ac[r] != ac[r - 1]:
            res -= 1
        print(res if res >= 0 else 0)
    # return res


main()

Submission status: Wrong Answer

Solution code:
def c_get_ac(N, Q, S, I):
    dp = [0] * N
    count = 0
    for k, c in enumerate(S):
        if c == 'C':
            if k != 0 and S[k - 1] == 'A':
                count += 1
                dp[k] += count
        else:
            dp[k] += count

    ans_tmp = []
    for l, r in I:
        ans_tmp.append(dp[r - 1] - dp[l - 1])
    ans = '\n'.join(map(str, ans_tmp))
    return ans

N, Q = [int(i) for i in input().split()]
S = input()
I = [[int(i) for i in input().split()] for j in range(Q)]
print(c_get_ac(N, Q, S, I))

Submission status: Wrong Answer

Solution code:
import sys

N,Q=map(int,sys.stdin.readline().rstrip().split())
S=list(sys.stdin.readline().rstrip())
count = [0 for i in range(N)]
phase=0
csum=0
for i,c in enumerate(S):
    if c=='A' and phase==0:
        phase=1
    elif c=='C' and phase==1:
        csum+=1
        phase=0
    else:
        phase=0
    count[i]=csum
#print(count)
ans=[]
for i in range(Q):
    l,r=map(int,sys.stdin.readline().rstrip().split())
    ans.append(count[r-1]-count[l-1])
for a in ans:
    print(a)