Submission #75819743

---

Source Code Expand

import sys
input = sys.stdin.readline

n,q = map(int,input().split())
s = list(input().rstrip())
L,M = [],[0]
idx = 0
cur = s[0]
com = 1
for i in range(1,n):
    if s[i] == cur: com += 1
    else:
        L.append([idx,idx+com-1,cur])
        idx = i
        cur = s[i]
        com = 1
    M.append(len(L))
L.append([idx,idx+com-1,cur])

S = [0]
for i in range(len(L)):
    st,e,a = L[i]
    c = (e-st+1)//2
    if a == 'X': c = 0
    S.append(S[i]+c)

for _ in range(q):
    l,r = map(int,input().split())
    a,b = M[l-1],M[r-1]
    if a == b:
        if s[l-1] == 'X': print(0)
        else: print((r-l+1)//2)
    else:
        ans = 0
        if s[l-1] != 'X': ans += (L[a][1]-l+2)//2
        if s[r-1] != 'X': ans += (r-L[b][0])//2
        print(ans+S[b]-S[a+1])

Submission Info

Judge Result