Problem p02599 (python)

Fixed submission:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_add3(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    bit_add(a, i, n, x)
    bit_add(a, j, n, -x)
def bit_add4(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    while i < n:
        a[i] += x
        i += i & -i
    while j < n:
        a[j] -= x
        j += j & -j

def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    X = Q.bit_length()
    mask, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & mask

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add4(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_add3(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    bit_add(a, i, n, x)
    bit_add(a, j, n, -x)
def bit_add4(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    while i < n:
        a[i] += x
        i += i & -i
    while j < n:
        a[j] -= x
        j += j & -j

def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    X = Q.bit_length()
    mask, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = (r, i)
        Ac[i] = l
    Aq.sort()

    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q

    def f2():
        offset = 0
        for r, i in Aq:

            for j in range(offset, r):
                ci = Aa[j]
                j += 2

                j0 = dp[ci]
                bit_add4(bit, j0, j, N1, 1)
                #bit_add(bit, j0, N1, 1)
                #bit_add(bit, j, N1, -1)

                dp[ci] = j

            offset = r
            l = Ac[i]

            ans[i] = bit_sum(bit, l)
    f2()

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_add3(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    bit_add(a, i, n, x)
    bit_add(a, j, n, -x)
def bit_add4(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    while i < n:
        a[i] += x
        i += i & -i
    while j < n:
        a[j] -= x
        j += j & -j

def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    X = Q.bit_length()
    mask, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & mask

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add4(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            #bit_add2(bit, j0, j, N1, 1)
            bit_add(bit, j0, N1, 1)
            bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add2(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = max(N, Q).bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [0] * N
    for i in range(N):
        ci = next(it)-1
        Aa[i] = ci
    Aq, Ac = [None] * Q, [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r, i = arg >> X, arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        else:
            offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    A = [None] * (N+Q)
    B = [0] * N
    C = [None] * Q
    for i in range(N):
        ci = next(it)-1
        A[i] = i << (X+1) | i
        B[i] = ci
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        A[N+i] = r<< (X+1) | bc | i
        C[i] = l

    A.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    for arg in A:
        r = arg >> (X+1)
        cmd = arg & bc
        i = arg & b1
        if cmd == 0:
            ci = B[i]

            lo = N1 + dp[ci]
            hi = N1 + r

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = r + 1
            continue
        l = C[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)

    if Q == 3:
        raise 1

    A = [None] * (N+Q)
    for i in range(N):
        ci = next(it)-1
        A[i] = (i, 0, ci)
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        A[N+i] = (r, 1, l, i)

    A.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    for r, cmd, *arg in A:
        if cmd == 0:
            ci, = arg

            lo = N1 + dp[ci]
            hi = N1 + r

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1


            dp[ci] = r + 1
            continue

        l, i = arg
        num = 0
        j = l + N
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)

    if Q == 3:
        raise 1
    A = [None] * (N+Q)
    for i in range(N):
        ci = next(it)-1
        A[i] = (i, 0, ci)
    for i in range(Q):
        l, r = next(it) - 1, next(it) - 1
        A[N+i] = (r, 1, l, i)

    A.sort()
    dp = [-1] * N
    dp2 = [0] * N

    ans = [0] * Q
    for r, cmd, *arg in A:
        if cmd == 0:
            ci, = arg
            for j in range(dp[ci], r):
                dp2[j+1] += 1
            dp[ci] = r
            continue

        l, i = arg
        ans[i] = dp2[l]

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


if __name__ == "__main__":
    resolve()