Problem:


Score : 600 points

Problem Statement

Let us consider the following operations on a string consisting of A and B:

Select a character in a string. If it is A, replace it with BB. If it is B, replace with AA.

Select a substring that is equal to either AAA or BBB, and delete it from the string.

For example, if the first operation is performed on ABA and the first character is selected, the string becomes BBBA.
If the second operation is performed on BBBAAAA and the fourth through sixth characters are selected, the string becomes BBBA.

These operations can be performed any number of times, in any order.

You are given two string S and T, and q queries a_i, b_i, c_i, d_i.
For each query, determine whether S_{a_i} S_{{a_i}+1} ... S_{b_i}, a substring of S, can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, a substring of T.

Constraints

1 \leq |S|, |T| \leq 10^5

S and T consist of letters A and B.

1 \leq q \leq 10^5

1 \leq a_i \leq b_i \leq |S|

1 \leq c_i \leq d_i \leq |T|

Input

Input is given from Standard Input in the following format:

S
T
q
a_1 b_1 c_1 d_1
...
a_q b_q c_q d_q

Output

Print q lines. The i-th line should contain the response to the i-th query. If S_{a_i} S_{{a_i}+1} ... S_{b_i} can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, print YES. Otherwise, print NO.

Sample Input 1

BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4

Sample Output 1

YES
NO
YES
NO

The first query asks whether the string ABA can be made into BBBA.
As explained in the problem statement, it can be done by the first operation.

The second query asks whether ABA can be made into BBBB, and the fourth query asks whether BBBAAAA can be made into BBB.
Neither is possible.

The third query asks whether the string BBBAAAA can be made into BBBA.
As explained in the problem statement, it can be done by the second operation.

Sample Input 2

AAAAABBBBAAABBBBAAAA
BBBBAAABBBBBBAAAAABB
10
2 15 2 13
2 13 6 16
1 13 2 20
4 20 3 20
1 18 9 19
2 14 1 11
3 20 3 15
6 16 1 17
4 18 8 20
7 20 3 14

Sample Output 2

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO



Sample input:
BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4


Sample output:
YES
NO
YES
NO

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

S = ins()
T = ins()
conv = {"A": 1, "B": 2}


def solve():
    cums = [0] * (len(S) + 1)
    cumt = [0] * (len(T) + 1)
    for i, x in enumerate(S):
        c = conv[x]  # 1 or 2
        cums[i + 1] = (cums[i] + c) % 3
    for i, x in enumerate(T):
        c = conv[x]  # 1 or 2
        cumt[i + 1] = (cumt[i] + c) % 3

    q = ini()
    for i in range(q):
        a, b, c, d = inm()
        if (cums[b] - cums[a - 1]) % 3 == (cumt[d] - cumt[c - 1]) % 3:
            print("YES")
        else:
            print("NO")


solve()

Submission status: Accepted

Solution code:
S = input()
T = input()
n = len(S)
m = len(T)
L = [0]*(n+1)
R = [0]*(m+1)
for i, s in enumerate(S):
  if s == "A":
    L[i+1] = (L[i]+1)%3
  else:
    L[i+1] = (L[i]-1)%3
for i, t in enumerate(T):
  if t == "A":
    R[i+1] = (R[i]+1)%3
  else:
    R[i+1] = (R[i]-1)%3
q = int(input())
for _ in range(q):
  a, b, c, d = map(int, input().split())
  if (L[b]-L[a-1])%3 == (R[d]-R[c-1])%3:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline


def solve():
    S, T = input(), input()
    q = int(input())

    ls, lt = len(S), len(T)
    acs, act = [0]*(ls+1), [0]*(lt+1)

    for i in range(1, ls+1):
        acs[i] = acs[i-1] + (S[i-1]=="A")
    for i in range(1, lt+1):
        act[i] = act[i-1] + (T[i-1]=="A")

    for _ in range(q):
        a, b, c, d = map(int, input().split())
        print("YES" if (acs[b]-acs[a-1]+b-a+1)%3==(act[d]-act[c-1]+d-c+1)%3 else "NO")


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline


def solve():
    S, T = input(), input()
    q = int(input())

    ls, lt = len(S), len(T)
    acs, act = [0]*(ls+1), [0]*(lt+1)

    for i in range(1, ls+1):
        acs[i] = acs[i-1] + (S[i-1]=="A")
    for i in range(1, lt+1):
        act[i] = act[i-1] + (T[i-1]=="A")

    for _ in range(q):
        a, b, c, d = map(int, input().split())
        print("YES" if (acs[b]-acs[a-1]+b-a+1)%3==(act[d]-act[c-1]+d-c+1)%3 else "NO")

solve()

Submission status: Accepted

Solution code:
S, T = input(), input()
q = int(input())

ls, lt = len(S), len(T)
acs, act = [0]*(ls+1), [0]*(lt+1)

for i in range(1, ls+1):
    acs[i] = acs[i-1] + (S[i-1]=="A")
for i in range(1, lt+1):
    act[i] = act[i-1] + (T[i-1]=="A")

for _ in range(q):
    a, b, c, d = map(int, input().split())
    print("YES" if (acs[b]-acs[a-1]+b-a+1)%3==(act[d]-act[c-1]+d-c+1)%3 else "NO")

Submission status: Accepted

Solution code:
S, T = input(), input()
q = int(input())

ls, lt = len(S), len(T)
acs, act = [0]*(ls+1), [0]*(lt+1)

for i in range(1, ls+1):
    acs[i] = acs[i-1] + (S[i-1]=="A")
for i in range(1, lt+1):
    act[i] = act[i-1] + (T[i-1]=="A")

for _ in range(q):
    a, b, c, d = map(int, input().split())
    sa = acs[b]-acs[a-1]
    sb = b-a+1-sa
    ta = act[d]-act[c-1]
    tb = d-c+1-ta
    print("YES" if (2*sa+sb)%3==(2*ta+tb)%3 else "NO")

Submission status: Accepted

Solution code:
from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


def main():
    S = input()
    T = input()
    treeS = SegTree(len(S), 0)
    treeT = SegTree(len(T), 0)
    treeS.set_list([1 if s=="A" else 0 for s in S])
    treeT.set_list([1 if s=="A" else 0 for s in T])

    q = int(input())
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        sa = treeS.get(a-1, b)
        sb = b-a+1-sa
        ta = treeT.get(c-1, d)
        tb = d-c+1-ta

        if (2*(sb-sa)+tb-ta)%3 or (sb-sa+2*(tb-ta))%3:
            print("NO")
        else:
            print("YES")

main()

Submission status: Accepted

Solution code:
S=input()
T=input()
N=int(input())
abcd = [tuple(map(int,input().split())) for _ in range(N)]

NS = len(S)
NT = len(T)
cs0 = [0]*(NS+1)
cs1 = [0]*(NS+1)
ct0 = [0]*(NT+1)
ct1 = [0]*(NT+1)
for i in range(NS):
    cs0[i+1] = cs0[i]
    cs1[i+1] = cs1[i]
    if S[i]=='A':
        cs0[i+1] += 1
    else:
        cs1[i+1] += 1
for i in range(NT):
    ct0[i+1] = ct0[i]
    ct1[i+1] = ct1[i]
    if T[i]=='A':
        ct0[i+1] += 1
    else:
        ct1[i+1] += 1

for a,b,c,d in abcd:
    anum = cs0[b] - cs0[a-1]
    bnum = cs1[b] - cs1[a-1]
    num = 0
    if anum%3 == bnum%3 == 0:
        num = 0
    elif anum > bnum:
        num = (anum-bnum)%3
    else:
        num = 2*(bnum-anum)%3
    anum2 = ct0[d] - ct0[c-1]
    bnum2 = ct1[d] - ct1[c-1]
    num2 = 0
    if anum2%3 == bnum2%3 == 0:
        num2 = 0
    elif anum2 > bnum2:
        num2 = (anum2-bnum2)%3
    else:
        num2 = 2*(bnum2-anum2)%3
    
    if num == num2:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
import numpy as np

S = list(input())
T = list(input())

count_A_S = np.r_[[0], np.array(S) == 'A']
count_A_S = count_A_S.cumsum()
count_B_S = np.r_[[0], np.array(S) == 'B']
count_B_S = count_B_S.cumsum()
count_A_T = np.r_[[0], np.array(T) == 'A']
count_A_T = count_A_T.cumsum()
count_B_T = np.r_[[0], np.array(T) == 'B']
count_B_T = count_B_T.cumsum()

def check(a1, b1, a2, b2):
  if a1 < a2:
    if b1 < b2:
      diff1 = a2 - a1; diff2 = b2 - b1
      diff = abs(diff1 - diff2)
    else:
      diff = b1 - b2 + a2 - a1
  else:
    if b1 < b2:
      diff = a1 - a2 + b2 - b1
    else:
      diff1 = a1 - a2; diff2 = b1 - b2
      diff = abs(diff1 - diff2)
  if diff % 3 == 0:
    return 'YES'
  else:
    return 'NO'

q = int(input())
ans = []
for i in range(q):
  a, b, c, d = map(int, input().split())
  num_a_s = count_A_S[b] - count_A_S[a-1]
  num_b_s = count_B_S[b] - count_B_S[a-1]
  num_a_t = count_A_T[d] - count_A_T[c-1]
  num_b_t = count_B_T[d] - count_B_T[c-1]
  ans.append(check(num_a_s, num_b_s, num_a_t, num_b_t))

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# ARC071E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


s = input()
t = input()

sa = [0] * (len(s)+1)
sb = [0] * (len(s)+1)
ta = [0] * (len(t)+1)
tb = [0] * (len(t)+1)

ca = 0
cb = 0
for i,c in enumerate(s):
    if c=="A":
        ca += 1
    else:
        cb += 1
    sa[i+1] = ca
    sb[i+1] = cb
ca = 0
cb = 0
for i,c in enumerate(t):
    if c=="A":
        ca += 1
    else:
        cb += 1
    ta[i+1] = ca
    tb[i+1] = cb


q = int(input())
for i in range(q):
    a,b,c,d = map(lambda x: int(x)-1, input().split())
    if (((sa[b+1]-sa[a]) - (sb[b+1]-sb[a])) - ((ta[d+1]-ta[c]) - (tb[d+1]-tb[c])))%3==0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
S=input();T=input()
dps=[0]*len(S)
for i in range(len(S)):
    if S[i]=="A":
        dps[i]+=1
    if i!=0:
        dps[i]+=dps[i-1]

dpt=[0]*len(T)
for i in range(len(T)):
    if T[i]=="A":
        dpt[i]+=1
    if i!=0:
        dpt[i]+=dpt[i-1]
dps=[0]+dps
dpt=[0]+dpt

q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    sc=dps[b]-dps[a-1]
    sa=sc-(b-a+1-sc)
    tc=dpt[d]-dpt[c-1]
    ta=tc-(d-c+1-tc)
    if sa%3==ta%3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
T = '-' + sr()
Q = ir()
cnt_S = np.array([[0, 0] for _ in range(len(S))])
cnt_T = np.array([[0, 0] for _ in range(len(S))])
for i, s in enumerate(S[1:], 1):
    if s == 'A':
        cnt_S[i][0] = 1
    else:
        cnt_S[i][1] = 1

for i, t in enumerate(T[1:], 1):
    if t == 'A':
        cnt_T[i][0] = 1
    else:
        cnt_T[i][1] = 1

np.add.accumulate(cnt_S, axis=0, out=cnt_S)
np.add.accumulate(cnt_T, axis=0, out=cnt_T)

answer = []
for _ in range(Q):
    a, b, c, d = lr()
    num_S = cnt_S[b][0] - cnt_S[b][1] - (cnt_S[a-1][0] - cnt_S[a-1][1])
    num_T = cnt_T[d][0] - cnt_T[d][1] - (cnt_T[c-1][0] - cnt_T[c-1][1])
    if (num_S - num_T) % 3 == 0:
        answer.append('YES')
    else:
        answer.append('NO')

print('\n'.join(answer))
# 58

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
T = '-' + sr()
Q = ir()
cnt_S = np.array([[0, 0] for _ in range(len(S))])
cnt_T = np.array([[0, 0] for _ in range(len(S))])
for i, s in enumerate(S[1:], 1):
    if s == 'A':
        cnt_S[i][0] = 1
    else:
        cnt_S[i][1] = 1

for i, t in enumerate(T[1:], 1):
    if t == 'A':
        cnt_T[i][0] = 1
    else:
        cnt_T[i][1] = 1

np.add.accumulate(cnt_S, axis=0, out=cnt_S)
np.add.accumulate(cnt_T, axis=0, out=cnt_T)

for _ in range(Q):
    a, b, c, d = lr()
    num_S = cnt_S[b][0] - cnt_S[b][1] - (cnt_S[a-1][0] - cnt_S[a-1][1])
    num_T = cnt_T[d][0] - cnt_T[d][1] - (cnt_T[c-1][0] - cnt_T[c-1][1])
    if (num_S - num_T) % 3 == 0:
        print('YES')
    else:
        print('NO')

# 58

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

S=input()
T=input()
SAdata=[int(S[i]=="A") for i in range(len(S))]
SBdata=[int(S[i]=="B") for i in range(len(S))]
for i in range(1,len(S)):
    SAdata[i]+=SAdata[i-1]
for i in range(1,len(S)):
    SBdata[i]+=SBdata[i-1]
SAdata.append(0)
SBdata.append(0)

TAdata=[int(T[i]=="A") for i in range(len(T))]
TBdata=[int(T[i]=="B") for i in range(len(T))]
for i in range(1,len(T)):
    TAdata[i]+=TAdata[i-1]
for i in range(1,len(T)):
    TBdata[i]+=TBdata[i-1]
TAdata.append(0)
TBdata.append(0)

q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    SA=SAdata[b-1]-SAdata[a-2]
    SB=SBdata[b-1]-SBdata[a-2]
    TA=TAdata[d-1]-TAdata[c-2]
    TB=TBdata[d-1]-TBdata[c-2]
    if (SA-SB)%3==(TA-TB)%3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
S = input()
T = input()
Q = int(input())

nS = [[0, 0]]
nT = [[0, 0]]

for i, c in enumerate(S):
  nS.append([abs(ord(c) - ord('A')), abs(ord(c) - ord('B'))])
  nS[i + 1][0] += nS[i][0]
  nS[i + 1][1] += nS[i][1]

for i, c in enumerate(T):
  nT.append([abs(ord(c) - ord('A')), abs(ord(c) - ord('B'))])
  nT[i + 1][0] += nT[i][0]
  nT[i + 1][1] += nT[i][1]

for qawsedrftgyhujikolp in range(Q):
  a, b, c, d = map(int, input().split())
  if (nS[b][0] - nS[a - 1][0] + 2 * nS[b][1] - 2 * nS[a - 1][1]) % 3 == (nT[d][0] - nT[c - 1][0] + 2 * nT[d][1] - 2 * nT[c - 1][1]) % 3:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
s = input()
t = input()
q = int(input())
ans = ['YES']*q

scnt = [[0]*(len(s)+1) for _ in range(2)]
tcnt = [[0]*(len(t)+1) for _ in range(2)]

for i,S in enumerate(s):
    scnt[0][i+1] = scnt[0][i]
    scnt[1][i+1] = scnt[1][i]
    scnt[ord(S)-ord('A')][i+1] += 1

for i,T in enumerate(t):
    tcnt[0][i+1] = tcnt[0][i]
    tcnt[1][i+1] = tcnt[1][i]
    tcnt[ord(T)-ord('A')][i+1] += 1

for i in range(q):
    a,b,c,d = map(int,input().split())
    a -= 1
    c -= 1
    A = scnt[0][b] - scnt[0][a] - tcnt[0][d] + tcnt[0][c]
    B = scnt[1][b] - scnt[1][a] - tcnt[1][d] + tcnt[1][c]
    if (A-B)%3 != 0:
        ans[i] = 'NO'
print('\n'.join(ans))

Submission status: Accepted

Solution code:
s = input()
t = input()
n, m = len(s), len(t)
a = [0] * (n + 1)
b = [0] * (m + 1)
for i in range(n):
    a[i + 1] = a[i]
    if s[i] == 'A':
        a[i + 1] += 1
    else:
        a[i + 1] += 2
for i in range(m):
    b[i + 1] = b[i]
    if t[i] == 'A':
        b[i + 1] += 1
    else:
        b[i + 1] += 2
q = int(input())
for _ in range(q):
    i, j, k, l = map(int, input().split())
    if (a[j] - a[i - 1]) % 3 == (b[l] - b[k - 1]) % 3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
s = input()[:-1]
t = input()[:-1]
d = {"A": 1, "B": 2}
ds = [0] + list(accumulate([d[x] for x in s]))
dt = [0] + list(accumulate([d[x] for x in t]))
ans = []
append=ans.append
for _ in range(int(input())):
	a, b, c, d = map(int, input().split())
	if (ds[b]-ds[a-1])%3==(dt[d]-dt[c-1])%3:
		append("YES")
	else:
		append("NO")
print("\n".join(ans))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# ((Aの数)-(Bの数))%3 が同じときだけ可能

S = list(input())
T = list(input())
q = I()
a,b,c,d = LIR(q,4)

n = len(S)
Sab = [0]*(n+1)
for i in range(n):
    if S[i] == 'A':
        Sab[i+1] = Sab[i]+1
    else:
        Sab[i+1] = Sab[i]-1

m = len(T)
Tab = [0]*(m+1)
for i in range(m):
    if T[i] == 'A':
        Tab[i+1] = Tab[i]+1
    else:
        Tab[i+1] = Tab[i]-1

for i in range(q):
    diff = (Sab[b[i]]-Sab[a[i]-1]) - (Tab[d[i]]-Tab[c[i]-1])
    if diff%3 == 0:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]
acc0, acc1 = [0]*(len(S)+1), [0]*(len(S)+1)

for i in range(len(S)):
    acc0[i+1] = acc0[i]+(1 if S[i]=='A' else 0)
    acc1[i+1] = acc1[i]+(1 if S[i]=='B' else 0)

acc2, acc3 = [0]*(len(T)+1), [0]*(len(T)+1)

for i in range(len(T)):
    acc2[i+1] = acc2[i]+(1 if T[i]=='A' else 0)
    acc3[i+1] = acc3[i]+(1 if T[i]=='B' else 0)

q = int(input())

for _ in range(q):
    a, b, c, d = map(int, input().split())
    A_diff = acc0[b]-acc0[a-1]-(acc2[d]-acc2[c-1])
    B_diff = acc1[b]-acc1[a-1]-(acc3[d]-acc3[c-1])
    
    if A_diff%3==B_diff%3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

S = input()
T = input()
cntS = [1 if S[i] == 'A' else -1 for i in range(len(S))]
cntT = [1 if T[i] == 'A' else -1 for i in range(len(T))]
cumS = list(accumulate([0] + cntS))
cumT = list(accumulate([0] + cntT))
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    if (cumS[b] - cumS[a-1]) % 3 == (cumT[d] - cumT[c-1]) % 3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
S = input()
T = input()

accSA = [0] * (len(S) + 1)
accSB = [0] * (len(S) + 1)

for i, s in enumerate(S):
    accSA[i + 1] += accSA[i]
    accSB[i + 1] += accSB[i]
    if s == 'A':
        accSA[i + 1] += 1
    else:
        accSB[i + 1] += 1

accTA = [0] * (len(T) + 1)
accTB = [0] * (len(T) + 1)

for i, s in enumerate(T):
    accTA[i + 1] += accTA[i]
    accTB[i + 1] += accTB[i]
    if s == 'A':
        accTA[i + 1] += 1
    else:
        accTB[i + 1] += 1

Q = int(input())
ans = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())

    sA = accSA[b] - accSA[a - 1]
    sB = accSB[b] - accSB[a - 1]
    tA = accTA[d] - accTA[c - 1]
    tB = accTB[d] - accTB[c - 1]

    sA = (sA + sB * 2) % 3
    tA = (tA + tB * 2) % 3

    ans.append('YES' if sA == tA else 'NO')
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
S = input()
T = input()

q = int(input())

s = [0]*len(S)
t = [0]*len(T)
for i, x in enumerate(S):
    if x == "A":
        s[i] += 1
for i, x in enumerate(T):
    if x == "A":
        t[i] += 1

ss = [0]*(len(S)+1)
for i, x in enumerate(s):
    ss[i+1] = s[i] + ss[i]
tt = [0]*(len(T) + 1)
for i, x in enumerate(t):
    tt[i+1] = t[i]+tt[i]


for i in range(q):
    a, b, c, d = map(int, input().split())

    k = (ss[b] - ss[a-1])
    l = (tt[d] - tt[c-1])
    k += ((b - a + 1) - k)*2
    l += ((d - c + 1) - l)*2
    if abs(k-l) % 3 == 0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
s=input()
t=input()
q=int(input())
x=[1 if s[i]=='B' else 2 for i in range(len(s))]
y=[1 if t[i]=='B' else 2 for i in range(len(t))]
for i in range(1,len(s)):
  x[i]+=x[i-1]
for i in range(1,len(t)):
  y[i]+=y[i-1]

for i in range(q):
  a,b,c,d=map(int,input().split())
  u=x[b-1]-(x[a-2] if 2<=a else 0)
  v=y[d-1]-(y[c-2] if 2<=c else 0)
  print('YES' if u%3==v%3 else 'NO')

Submission status: Accepted

Solution code:
S, T, q, *L = open(0).read().split()
sa = [0]
sb = [0]
ta = [0]
tb = [0]
for c in S:
  if c=='A':
    sa.append(sa[-1]+1)
    sb.append(sb[-1])
  else:
    sa.append(sa[-1])
    sb.append(sb[-1]+1)
for c in T:
  if c=='A':
    ta.append(ta[-1]+1)
    tb.append(tb[-1])
  else:
    ta.append(ta[-1])
    tb.append(tb[-1]+1)
for a,b,c,d in zip(*[iter(map(int,L))]*4):
  nsa = sa[b]-sa[a-1]
  nsb = sb[b]-sb[a-1]
  nta = ta[d]-ta[c-1]
  ntb = tb[d]-tb[c-1]
  mb = ntb-nsb
  ma = nta-nsa
  if (2*mb+ma)%3==(2*ma+mb)%3==0:
    print('YES')
  else:
    print('NO')

Submission status: Accepted

Solution code:
s=input()
t=input()
q=int(input())
n=len(s)
pre=[0]*(n+1)
for i in range(n):
    if s[i]=="A":
        pre[i]=pre[i-1]+1
    else:
        pre[i]=pre[i-1]
m=len(t)
p=[0]*(m+1)
for i in range(m):
    if t[i]=="A":
        p[i]=p[i-1]+1
    else:
        p[i]=p[i-1]

for _ in range(q):
    a,b,c,d=map(lambda x:int(x)-1,input().split())

    aa=(pre[b]-pre[a-1])
    co=(b-a+1-aa)
    co+=aa*2

    bb=(p[d]-p[c-1])
    do=(d-c+1-bb)
    do+=bb*2
   # print(aa,bb,co,do)
    co%=3
    do%=3
    if co==do:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = list(input())[: -1]
T = list(input())[: -1]
css = [0] * (len(S) + 1)
cst = [0] * (len(T) + 1)

for i in range(len(S)): css[i + 1] = css[i] + (S[i] == "A") + (S[i] == "B") * 2
for i in range(len(T)): cst[i + 1] = cst[i] + (T[i] == "A") + (T[i] == "B") * 2

#print(css, cst)

for _ in range(int(input())):
  a, b, u, v = map(int, input().split())
  if (css[b] - css[a - 1]) % 3 == (cst[v] - cst[u - 1]) % 3: print("YES")
  else: print("NO")

Submission status: Accepted

Solution code:
from itertools import accumulate

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

SL = [1 if s == "A" else 2 for s in S]
TL = [1 if t == "A" else 2 for t in T]

AcumS = [0] + list(accumulate(SL))
AcumT = [0] + list(accumulate(TL))

for a, b, c, d in ABCD:
    s = AcumS[b] - AcumS[a - 1]
    t = AcumT[d] - AcumT[c - 1]
    if (s - t) % 3 == 0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = [ord(s)-65 for s in input()]
T = [ord(t)-65 for t in input()]

acc1 = [0] + list(accumulate(S))
acc2 = [0] + list(accumulate(T))

# 3つのタイプを判定(0: aが残る, 1: bが残る, 2: 何も残らない)
def check(cnta, cntb):
    if cnta == cntb:
        return 2
    elif cnta < cntb:
        cntb -= cnta
        if cntb % 3 == 0:
            return 2
        elif cntb % 3 == 1:
            return 1
        else:
            return 0
    else:
        cnta -= cntb
        if cnta % 3 == 0:
            return 2
        elif cnta % 3 == 1:
            return 0
        else:
            return 1

Q = INT()
for _ in range(Q):
    l1, r1, l2, r2 = MAP()

    ln1 = r1 - l1 + 1
    ln2 = r2 - l2 + 1
    # 累積和を使ってO(1)でAとBの個数を取得
    cntb1 = acc1[r1] - acc1[l1-1]
    cnta1 = ln1 - cntb1
    cntb2 = acc2[r2] - acc2[l2-1]
    cnta2 = ln2 - cntb2
    # 同じタイプかどうか判定する
    if check(cnta1, cntb1) == check(cnta2, cntb2):
        YES()
    else:
        NO()

Submission status: Accepted

Solution code:
from itertools import accumulate
s = list(input().replace("A","1").replace("B","2"))
t = list(input().replace("A","1").replace("B","2"))
s = list(map(int,s))
t = list(map(int,t))
accs = [0]+list(accumulate(s))
acct = [0]+list(accumulate(t))
q = int(input())
abcd = [list(map(int,input().split())) for i in range(q)]
for a,b,c,d in abcd:
  if (accs[b]-accs[a-1])%3 == (acct[d]-acct[c-1])%3:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
from itertools import accumulate

s = input()
t = input()
q = int(input())
abcd = [tuple(map(int,input().split())) for i in range(q)]

s_number = [2 if ab == 'B' else 1 for ab in s]
t_number = [2 if ab == 'B' else 1 for ab in t]

s_sum = [0] + s_number
s_sum = list(accumulate(s_sum))

t_sum = [0] + t_number
t_sum = list(accumulate(t_sum))

for a,b,c,d in abcd:

    s_i = s_sum[b]-s_sum[a-1]
    t_i = t_sum[d]-t_sum[c-1]

    if s_i%3 == t_i%3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 解説見ちゃった...
def main():
    s = SI()
    t = SI()
    s = [0] + [x for x in accumulate([1 if c == "A" else 2 for c in s])]
    t = [0] + [x for x in accumulate([1 if c == "A" else 2 for c in t])]
    q = II()
    for _ in range(q):
        a, b, c, d = MI()
        if (s[b] - s[a - 1]) % 3 == (t[d] - t[c - 1]) % 3: print("YES")
        else: print("NO")

main()

Submission status: Accepted

Solution code:
S = input()
T = input()
q = int(input())
L = [[int(l) for l in input().split()] for _ in range(q)]

sumS = [0]*(len(S)+1)
sumT = [0]*(len(T)+1)

for i in range(len(S)):
    if S[i] == "A":
        sumS[i+1] += 1
    sumS[i+1] += sumS[i]

for i in range(len(T)):
    if T[i] == "A":
        sumT[i+1] += 1
    sumT[i+1] += sumT[i]

for i in range(q):
    a = (sumT[L[i][3]]-sumT[L[i][2]-1]) - (sumS[L[i][1]]-sumS[L[i][0]-1])
    b = (L[i][3]-L[i][2]+1) - (L[i][1]-L[i][0]+1) - a
    if (a-b)%3 == 0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
def examC():
    N = I()
    d = defaultdict(int)
    for i in range(N):
        curD = defaultdict(int)
        S = SI()
        for s in S:
            curD[s]+=1
        if i==0:
            d = curD
            continue
        for s in alphabet:
            d[s] = min(d[s],curD[s])
    d = sorted(d.items())
    ans = ""
    for key,i in d:
        ans +=key*i
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); Y = LI()
    distX = [0]*N; distY = [0]*M
    for i in range(N-1):
        distX[i+1] = X[i+1]-X[i]
    for i in range(M-1):
        distY[i+1] = Y[i+1]-Y[i]
    numX = [0]*N; numY = [0]*M
    for i in range(N):
        numX[i] = i*(N-i)
    for i in range(M):
        numY[i] = i*(M-i)
    LX = 0; LY = 0
    for i in range(N):
        LX += distX[i]*numX[i]
        LX %= mod
    for i in range(M):
        LY += distY[i]*numY[i]
        LY %= mod
#    print(numX,distX); print(numY,distY)
    ans = (LX*LY) % mod
    print(ans)
    return

def examE():
    S = SI(); T = SI()
    numaS = [0]*(len(S)+1)
    numaT = [0]*(len(T)+1)
    for i,s in enumerate(S):
        numaS[i+1] = numaS[i]
        if s=="A":
            numaS[i+1] +=1
    for i,s in enumerate(T):
        numaT[i+1] = numaT[i]
        if s=="A":
            numaT[i+1] +=1
#    print(numaS); print(numaT)
    Q = I()
    ans = ["YES"]*Q
    for i in range(Q):
        a,b,c,d = LI()
        curaS = numaS[b] - numaS[a-1]
        curbS = (b-a)-curaS+1
        curaT = numaT[d] - numaT[c-1]
        curbT = (d-c)-curaT+1
#        print(curaS,curbS,curaT,curbT)
        if (curaS%3+(curaS+curbS)%3)%3 != (curaT%3+(curaT+curbT)%3)%3:
#            if (curbS % 3 + (curaS + curbS) % 3) % 3 != (curbT % 3 + (curaT + curbT) % 3) % 3:
            ans[i]="NO"
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
# import sys
# sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def main():
    s = input()
    t = input()
    q = int(input())
    sa = [0]*(len(s)+1)
    sb = [0]*(len(s)+1)
    ta = [0]*(len(t)+1)
    tb = [0]*(len(t)+1)
    for i in range(1 , len(s)+1):
        if s[i-1] == "A":
            sa[i] = sa[i - 1] + 1
        else:
            sa[i] = sa[i - 1]

        if s[i-1] == "B":
            sb[i] = sb[i - 1] + 1
        else:
            sb[i] = sb[i - 1]

    for i in range(1,len(t)+1):
        if t[i-1] == "A":
            ta[i] = ta[i - 1] + 1
        else:
            ta[i] = ta[i - 1]

        if t[i-1] == "B":
            tb[i] = tb[i - 1] + 1
        else:
            tb[i] = tb[i - 1]

    for i in range(q):
        a, b, c, d = map(int, input().split())
        sl, sr = (sa[b] - sa[a - 1]) % 3, (sb[b] - sb[a - 1]) % 3
        tl, tr = (ta[d] - ta[c - 1]) % 3, (tb[d] - tb[c - 1]) % 3
        sl += sr * 2
        tl += tr * 2
        sl %= 3
        tl %= 3
        if sl == tl:
            print("YES")
        else:
            print("NO") 
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
yes = "YES"
no = "NO"
s=input()
t=input()
ls=[0]
lt=[0]
p=0
for c in s:
    if c == "A":p += 1
    else:p-= 1
    ls.append(p)
p=0
for c in t:
    if c == "A":p += 1
    else:p-= 1
    lt.append(p)

q=int(input())
for _ in range(q):
    a,b,c,d = map(int,input().split())
    if (ls[b]-ls[a-1])%3 == (lt[d]-lt[c-1])%3:print(yes)
    else:print(no)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc071/submissions/6325840

from itertools import accumulate

convert = {'A': 1, 'B': 2}
S = tuple(convert[x] for x in input())
T = tuple(convert[x] for x in input())
# 最速:   convert
# 次点:   *A, = map()
# 最下位: A = tuple(map())

acc_s = (0,) + tuple(accumulate(S))
acc_t = (0,) + tuple(accumulate(T))

ans = []
Q = int(input())
for _ in range(Q):
    sl, sr, tl, tr = map(int, input().split())
    # 添え字-1は変数再代入しない方が20ms速い
    ans.append('YES' if ((acc_t[tr] - acc_t[tl - 1]) - (acc_s[sr] - acc_s[sl - 1])) % 3 == 0 else 'NO')

print(*ans, sep='\n')
# 逐次printだと1000ms
# 一括だと500ms

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc071/submissions/6325840

from itertools import accumulate

convert = {'A': 1, 'B': 2}
S = tuple(convert[x] for x in input())
T = tuple(convert[x] for x in input())
# 最速:   convert
# 次点:   *A, = map()
# 最下位: A = tuple(map())

acc_s = (0,) + tuple(accumulate(S))
acc_t = (0,) + tuple(accumulate(T))

ans = []
Q = int(input())
for _ in range(Q):
    sl, sr, tl, tr = map(int, input().split())
    # 添え字-1は変数再代入しない方が20ms速い
    ans.append('YES' if (acc_t[tr] - acc_t[tl - 1]) % 3 == (acc_s[sr] - acc_s[sl - 1]) % 3 else 'NO')

print(*ans, sep='\n')
# 逐次printだと1000ms
# 一括だと500ms