Submission #903754

#	Time	Username	Problem	Language	Result	Execution time	Memory
903754		GolubevVA	Modern Machine (JOI23_ho_t5)	Pypy 3	0 / 100	73 ms	21900 KiB

Main

import sys
from bisect import bisect_right

class SegTree:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.N = 1
        while self.N < n:
            self.N <<= 1
        self.segs = [[] for _ in range(2 * self.N)]
        self.add = [[] for _ in range(2 * self.N)]

    def build(self, v, tl, tr, a):
        if tl + 1 == tr:
            if tl < self.n:
                self.segs[v] = [(0, a[tl] - 1), (a[tl], self.mod - 1)]
                self.add[v] = [a[tl] + 1 if a[tl] + 1 < self.mod else 0, a[tl]]
            else:
                self.segs[v] = [(0, self.mod - 1)]
                self.add[v] = [0]
            return
        m = tl + (tr - tl) // 2
        self.build(2 * v, tl, m, a)
        self.build(2 * v + 1, m, tr, a)
        for i in range(len(self.segs[2 * v])):
            l, r = self.segs[2 * v][i]
            nxt = l + self.add[2 * v][i]
            if nxt >= self.mod:
                nxt -= self.mod
            j = bisect_right(self.segs[2 * v + 1], (nxt, self.mod)) - 1
            while self.segs[2 * v + 1][j][1] - nxt < r - l:
                self.segs[v].append((l, l + self.segs[2 * v + 1][j][1] - nxt))
                self.add[v].append(self.add[2 * v][i] + self.add[2 * v + 1][j])
                if self.add[v][-1] >= self.mod:
                    self.add[v][-1] -= self.mod
                l = self.segs[v][-1][1] + 1
                nxt = l + self.add[2 * v][i]
                if nxt >= self.mod:
                    nxt -= self.mod
                j += 1
                if j == len(self.segs[2 * v + 1]):
                    j = 0
            self.segs[v].append((l, r))
            self.add[v].append(self.add[2 * v][i] + self.add[2 * v + 1][j])
            if self.add[v][-1] >= self.mod:
                self.add[v][-1] -= self.mod

    def build_tree(self, a):
        self.build(1, 0, self.N, a)

    def query(self, v, tl, tr, l, r, rocks):
        if l <= tl and tr <= r:
            pos = bisect_right(self.segs[v], (rocks, self.mod)) - 1
            rocks += self.add[v][pos]
            if rocks >= self.mod:
                rocks -= self.mod
            return rocks
        m = tl + (tr - tl) // 2
        if l < m:
            rocks = self.query(2 * v, tl, m, l, r, rocks)
        if m < r:
            rocks = self.query(2 * v + 1, m, tr, l, r, rocks)
        return rocks

    def query_tree(self, l, r, rocks):
        if l >= r:
            return rocks
        return self.query(1, 0, self.N, l, r, rocks)

def solve():
    n, m = map(int, input().split())
    s = input()
    posBPref, posRSuf = [], []
    for i in range(n):
        if s[i] == 'B':
            posBPref.append(i)
        else:
            posRSuf.append(i)
    posRSuf.reverse()
    posBPref.append(n)
    posRSuf.append(-1)
    a = list(map(int, input().split()))

    pref = [0] * (m + 1)
    prefLeq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
    prefReq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
    cntReq = [[0 for _ in range(maxlog)] for _ in range(m + 1)]
    for i in range(m):
        pref[i + 1] = pref[i] + a[i]
        for k in range(maxlog):
            prefLeq[i + 1][k] = prefLeq[i][k] + (a[i] <= (1 << k)) * a[i]
            prefReq[i + 1][k] = prefReq[i][k] + (a[i] > (n - (1 << k))) * a[i]
            cntReq[i + 1][k] = cntReq[i][k] + (a[i] > (n - (1 << k)))

    st = SegTree(m, n + 1)
    st.build_tree(a)

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        prefR = posBPref[0]
        sufB = n - posRSuf[0] - 1
        addPref = 0
        addSuf = 0

        if prefR == 0 and sufB == 0:
            makeStep(a[l], prefR, sufB, addPref, addSuf)
            l += 1
        while not collided(addPref, addSuf) and l < r:
            left, right = l, r + 1
            while right - left > 1:
                mid = left + (right - left) // 2
                if hasBad(prefR, sufB, l, mid):
                    right = mid
                else:
                    left = mid
            l = completeTillCollide(prefR, sufB, addPref, addSuf, l, left)
            if not collided(addPref, addSuf) and l < r:
                makeStep(a[l], prefR, sufB, addPref, addSuf)
                l += 1
        ans = 0
        if collided(addPref, addSuf):
            ans = st.query_tree(l, r, prefR)
        else:
            ans = len(posRSuf) - 1 + addPref - addSuf

        print(ans)
if __name__ == "__main__":
    ios_base_sync_with_stdio = False
    cin_tie = False
    cout_tie = False

    maxlog = 17
    maxn = 120001
    Log = [-1, 0] + [0] * (maxn - 2)
    for i in range(2, maxn):
        Log[i] = Log[i >> 1] + 1

    T = 1
    for _ in range(T):
        solve()

• Subtask 1: 0 / 3
• Subtask 2: 0 / 12
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21