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:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, Q = LI()
S = input()
LR = LRI(Q)

L = [0] * (N+1)
R = [0] * (N+1)

pls = 0
now_A = False
for i in range(N+1):
    if i == 0:
        continue

    if S[i-1] == "A":
        now_A = True
    
    if now_A and S[i-1] == "C":
        pls = 1
    else:
        pls = 0

    L[i-1] = L[i-2] + pls
    R[i] = R[i-1] + pls

for lr in LR:
    l, r = lr
    print(R[r] - L[l-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#2問目
NQ = input().split()
N,Q = int(NQ[0]), int(NQ[1])
S = input()
P = [input().split() for i in range(Q)]

#累積和
ruiseki = [0]*N
for i in range(1,N):
    if(S[i] == "C" and S[i-1] == "A"):
        print(i)
        ruiseki[i] = ruiseki[i-1] + 1
    else:
        ruiseki[i] = ruiseki[i-1]

for j in range(Q):
    print(ruiseki[int(P[j][1]) - 1] - ruiseki[int(P[j][0]) - 1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    if (l - 2 < 0):
        result = cum[r - 2] - cum[l - 1]
    else:
        result = cum[r - 2] - cum[l - 2]
    ans_list.append(result)
[print(ans) for ans in ans_list]

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    result = cum[r - 2] - cum[l - 1] + 1
    if cum[r - 2] == cum[l - 1]:
        result = 0
    ans_list.append(result)
[print(ans) for ans in ans_list]

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    result = cum[r - 2] - cum[l - 1] + 1
    if result == 1:
        result = 0
    ans_list.append(result)
[print(ans) for ans in ans_list]

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  l -= 1
  r -= 1
  ans = slr[r]-slr[l]
  if slr[r] == slr[r-1]:
    ans -= 1
  if slr[l] != slr[l-1]:
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  l -= 1
  r -= 1
  ans = slr[r]-slr[l]
  if r < N:
    if slr[r] == slr[r-1]:
      ans -= 1
  if slr[l] != slr[l-1]:
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  l -= 1
  r -= 1
  ans = slr[r]-slr[l]
  if r < 8:
    if slr[r] == slr[r-1]:
      ans -= 1
  if slr[l] != slr[l-1]:
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
nq = list(map(int,input().split()))
n = nq[0]
q = nq[1]
s = input()
lr = [map(int, input().split()) for _ in range(q)]
l, r = [list(i) for i in zip(*lr)]
print(l)
sam = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        sam[i+1] = sam[i] + 1
    else:
        sam[i+1] = sam[i]
for i in range(q):
    ans = sam[r[i]-1] - sam[l[i]-1]
    print(ans)

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

print(dp)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,q = readInts()
    s = input()
    nya = [0] * (n+1)# 累積和
    for i in range(n):
        if i+1 < n:
            if s[i] == 'A' and s[i+1] == 'C':
                nya[i+1] = nya[i] + 1
            else:
                nya[i+1] = nya[i]
    print(nya)
    for q_ in range(q):
        l,r = readInts()
        l -=1
        r -=1
        print(nya[r] - nya[l])


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N ,Q = map(int, input().split())
S = list(input())
ans = [0]*N
jdg = S[0]
cnt = 0
for i in range(1,N):
    if jdg == "A" and S[i] == "C":
        cnt += 1
        ans[i] = cnt
    else:
        jdg = S[i]
        ans[i] = cnt

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

Submission status: Wrong Answer

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

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


for l, r in lr:
    l -= 1
    r -= 1
    if S[l] == 'C':
        print(s[r] - s[l])
    else:
        print(s[r] - s[max(0, l - 1)])
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n, q = map(int,input().split())
s = input()

tmp = [0 for _ in range(n)]
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        tmp[i] = 1
        tmp[i + 1] = 3
print(tmp)

for i in range(q):
    l, r = map(int,input().split())
    ans = sum(tmp[l-1:r])
    if tmp[l-1] == 3:
        ans -= 3
    if tmp[r-1] == 1:
        ans -= 1
    print(ans // 4)

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    S = input()
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    A = [0]*N
    AC = [0]*N
    for i, s in enumerate(S):
        if i != 0:
            A[i] = A[i-1]
            AC[i] = AC[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            AC[i] = A[i]
    A = list([0] + A)
    S = list([0] + AC)
    for le, ri in LR:
        print(S[ri] - A[le-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    S = input()
    LR = [[int(i)-1 for i in input().split()] for j in range(Q)]
    A = [0]*N
    AC = [0]*N
    for i, s in enumerate(S):
        if i != 0:
            A[i] = A[i-1]
            AC[i] = AC[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            AC[i] = A[i]
    for le, ri in LR:
        print(AC[ri] - AC[le])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int,input().split())
S = input()
cnt = [0]
for i in range(len(S)-1):
    cnt.append(cnt[-1])
    if S[i] == 'A' and S[i+1] == 'C':
        cnt[-1] += 1
cnt = [0] + cnt
print(cnt)

for _ in range(Q):
    l, r = map(int,input().split())
    ans = cnt[r] - cnt[l-1]
    if 2 <= l and (S[l-2] == 'A' and S[l-1] == 'C'):
        ans -= 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N, Q = map(int,input().split())
S = input()
cnt = [0]
for i in range(len(S)-1):
    cnt.append(cnt[-1])
    if S[i] == 'A' and S[i+1] == 'C':
        cnt[-1] += 1
cnt = [0] + cnt
print(cnt)

for _ in range(Q):
    l, r = map(int,input().split())
    ans = cnt[r] - cnt[l-1]
    if S[l-2] == 'A' and S[l-1] == 'C':
        ans -= 1
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

mark = [0]*(N+1)

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

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

Submission status: Wrong Answer

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

# 累積和の配列を定義
mark = [0]*(N+1)

# markの0, 1番目は0
for i in range(2, N+1):
    if S[i-2] == 'A' and S[i-1] == 'C':
        mark[i] = mark[i-1] + 1
    else:
        mark[i] = mark[i-1]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S = str(input())
ans = 0
for i in range(len(S)):
    count = 0
    fr = 0
    if S[i] == "A" or "T" or "C" or "G":
        count += 1
        for j in range(i+1, len(S)):
            if fr == 0 and S[j] == "A"  or  S[j] == "T"  or  S[j] == "C"  or  S[j] == "G":  
                count += 1
                print(S[j])
            else:
                fr += 1
    if ans < count:
        ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
s=input()
lit=[]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        lit.append(i)
for i in range(q):
    l,r=map(int,input().split())
    susu,sasa=-1,-1
    for j in range(len(lit)):
        if susu==-1 and lit[j]>=l-1:
            susu=lit[j]
        if lit[j]<=r-1:
            sasa=lit[j]
    print((sasa-susu-1)//2+1)

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
s = input()
x = [0] * (n + 1)
a = False
p = 0
for i in range(n):
    if a:
        if s[i] == "C":
            p += 1
            
        elif s[i] != "A":
            a = False
    else:
        if s[i] == "A":
            a = True
        else:
            a = False
    x[i] = p

for i in range(q):
    a, b = map(int,input().split())
    print(x[b-1] - x[a-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()
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=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 = map(int,input().split())
s = list(input())
base = [0]*n
count = 0

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

base[n-1] = base[n-2]

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

Submission status: Wrong Answer

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

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

base[n-1] = base[n-2]

for i in range(q):
  l,r = map(int,input().split())
  ans = base[r-1] - base[l-1]
  
  if s[r-1] == "A":
    ans = ans - 1
  
  if s[l-1] == "A":
    ans = ans + 1
    
  print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

base[n-1] = base[n-2]

for i in range(q):
  l,r = map(int,input().split())
  ans = base[r-1] - base[l-1]
  
  if s[r-1] == "A":
    ans = ans - 1
    
  print(ans)

Submission status: Wrong Answer

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

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

for i in range(q):
  l,r = map(int,input().split())
  temp = base[(l-1):r]
  ans = sum(temp)
  
  if s[r-1] == "A":
    ans = ans - 1
    
  print(ans)

Submission status: Wrong Answer

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

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    if r - l == 1:
        ans.append(0)
        continue
    if l == 1:
        l = 2
    ans.append(cnt[r-1] - cnt[l-2])

print('\n'.join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
s = input()
af = False
AClist = [0 for i in range(10**5)]
for i,c in enumerate(s):
    if af:
        if c == 'C':
            AClist[i-1]+=1
        elif c != 'A':
            af = False
    else:
        if c == 'A':
            af = True

a2=[0]
for i in AClist:a2.append(a2[-1]+i)
def SumArea(l, r):
    return a2[r]-a2[l]

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

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
s = input()
af = False
AClist = [0 for i in range(10**5)]
for i,c in enumerate(s):
    if af:
        if c == 'C':
            AClist[i-1]+=1
        elif c != 'A':
            af = False
    else:
        if c == 'A':
            af = True

a2=[0]
for i in AClist:a2.append(a2[-1]+i)
def SumArea(l, r):
    return a2[r]-a2[l]

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

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
s = input()
af = False
AClist = [0 for i in range(10**5)]
for i,c in enumerate(s):
    if af:
        if c == 'C':
            AClist[i-1]+=1
        elif c != 'A':
            af = False
    else:
        if c == 'A':
            af = True

a2=[0]
for i in AClist:a2.append(a2[-1]+i)
def SumArea(l, r):
    return a2[r]-a2[l]


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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = input()
S = [c for c in S]
total = [0]*N
cnt = 0

flag = False
for i in range(N):
    if flag:
        if S[i]=='C':
            cnt += 1
        flag = False
    else:
        if S[i]=='A':
            flag = True
    total[i] = cnt

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
S = input()
ans = 0
ACGT = ["A","C","G","T"]
for i in range(len(S)):
    for j in range(i,len(S)+1):
        clipped_list = list(S[i:j])
        clipped = set(clipped_list)
        for acgt in ACGT:
            try:
                clipped.remove(acgt)
            except:
                pass
        if clipped == set():
            ans = max(ans,len(clipped_list))

print(ans)

Submission status: Wrong Answer

Solution code:
N,Q = [int(x) for x in input().split()]
s = input()
l = list(s)
rui = [0] * (N+1)
for i in range(2,len(l)+1):
    if l[i-2] == "A" and l[i-1] == "C":
        rui[i] = rui[i-1] + 1
    else:
        rui[i] = rui[i-1]
for i in range(Q):
    a,b = [int(x) for x in input().split()]
    print(rui[b]-rui[a])
print(rui)

Submission status: Wrong Answer

Solution code:
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]
print(lr)

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

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

print(AC)

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

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n,q = map(int, input().split())
    s = input()
    cumsum = list()

    for i in  range(n+1):
        if i == 0:
            cumsum.append(0)
        else:
            if i > 1 and  s[i-2:i] == 'AC':
                
                cumsum.append(cumsum[i-1] + 1)
            else:
                cumsum.append(cumsum[i-1])
    print(cumsum)
    for i in range(q):
        l,r = map(int, input().split())
        print(cumsum[r] - cumsum[l])
    
    return

if __name__ == '__main__':
    main()

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) # i文字目まででACが出現する数
  
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()

csum = [0,0]
for i in range(1, N):
    if S[i-1] + S[i] == 'AC':
        csum.append(csum[i-1] + 1)
    else:
        csum.append(csum[i])
print(csum)

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ans = [0 for _ in range(N+10)]

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

n = len(s)
L = 0
R = 1
cntAC = [0] * n

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

# 累積和
cSum = np.cumsum(cntAC)


for _lr in lr:
    if _lr[L] == 1:
        print(cSum[-1])
    else:
        print(cSum[_lr[R]-2] - cSum[_lr[L]-2])
        

"""
ACACTACG
"""

Submission status: Wrong Answer

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

ac_counts = [0 for _ in range(n + 1)]

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

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

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split()) 
q=input() 
l=[list(map(int,input().split())) for _ in range(m)] 
print(n,m,q,l) 
ans=0 
lst_j=[0]*(n+1) 
for i in range(n-1): 
	cnt=0 
	if q[i]+q[i+1]=="AC": 
		cnt=1 
		lst_j[i+1]=cnt+lst_j[i] 
	else:lst_j[i+1]=lst_j[i] 
for i,j in l: 
	ans=lst_j[j-1]-lst_j[i-1] 
	print(ans)

Submission status: Wrong Answer

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

ans=0 
cnt=0 
lst_j=[0]*(n-1) 
for i in range(n-1): 
	if q[i]+q[i+1]=="AC": 
		cnt=1 
		lst_j[i]=cnt 
		cnt=0 
	for i,j in l: 
		ans=lst_j[i-1:j-1].count(1) 
		print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

print(AC)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, q = MAP()
s = STR()
arr = [1 if s[i] + s[i + 1] == 'AC' else 0 for i in range(n - 1)]
arr2 = [0 for _ in range(n - 1)]
arr2[0] = arr[0]
for i in range(1, n - 1):
    arr2[i] = arr2[i - 1] + arr[i]
for _ in range(q):
    l, r = MAP()
    print(arr2[r - 2] - arr2[l - 1] + 1 if arr2[r - 2] - arr2[l - 1] != 0 else 0)

Submission status: Wrong Answer

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

for i in range(1, N):
    T[i+1] = T[i] + (1 if S[i-1:i+1]=='AC' else 0)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(T[r] - T[l])
print(T)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def bsearch(arr, num):
    r = len(arr) - 1
    l = 0
    while r - l > 1:
        c = (r + l) // 2
        if arr[c] > num:
            r = c
        elif arr[c] < num:
            l = c
        else:
            l = c
            r = c
            break
    return [l, r]

n, q = MAP()
s = STR()
index = []
for i in range(len(s) - 1):
    if s[i] + s[i + 1] == 'AC':
        index.append(i)
if len(index) > 1:
    for _ in range(q):
        l, r = MAP()
        ll = bsearch(index, l - 1)
        rr = bsearch(index, r - 2)
        lll = ll[0] if index[ll[0]] >= l - 1 else ll[1]
        rrr = rr[1] if index[rr[1]] <= r - 2 else rr[0]
        print(rrr - lll + 1)
elif len(index) == 1:
    t = index[0]
    for _ in range(q):
        l, r = MAP()
        if l - 1 <= t <= r - 2:
            print(1)
        else:
            print(0)
else:
    for _ in range(q):
        print(0)