Problem p03283 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class RectangleSum():
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.s = [[0] * (M+1) for _ in range(N+1)]

    def add(self, i, j, v):
        self.s[i+1][j+1] += v

    def build(self):
        for i in range(self.N+1):
            for j in range(self.M):
                self.s[i][j+1] += self.s[i][j]

        for i in range(self.N):
            for j in range(self.M+1):
                self.s[i+1][j] += self.s[i][j]

    def sum(self, i, j, h, w):
        ret = self.s[i][j]
        ret += self.s[i+h][j+w]
        ret -= self.s[i+h][j]
        ret -= self.s[i][j+w]

        return ret


@mt
def slv(N, M, Q, LR, PQ):
    rs = RectangleSum(N+1, N+1)
    for l, r in LR:
        rs.add(l, r, 1)

    rs.build()

    for p, q in PQ:
        print(rs.sum(p, p, q-p+1, q-p+1))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [set([]) for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i].add(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].add(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set([])
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl | vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, ('s', i))
        st.update(r, ('e', i))

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(map(lambda x: x[1], l)))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [0 for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] += 1
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] += self.__table[i]
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl + vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    ts = SegmentTree(N)
    te = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        ts.update(l, i)
        te.update(r, i)

    for p, q in PQ:
        ls = ts.query(0, p)
        re = te.query(q+1, N+1)
        print(ls, re)
        print(M-(ls+re))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)

    # N = 500
    # M = 2*(10**5)
    # Q = 10**5
    # LR = []
    # for _ in range(M):
    #     s = random.randint(1, N+1)
    #     e = random.randint(1, N+1)
    #     if s > e:
    #         s, e = e, s
    #     LR.append((s, e))
    # PQ = []
    # for _ in range(Q):
    #     s = random.randint(1, N+1)
    #     e = random.randint(1, N+1)
    #     if s > e:
    #         s, e = e, s
    #     PQ.append((s, e))
    # slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [[] for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i].append(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].append(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return []
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl + vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, i)
        st.update(r, i)

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(l))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log2(N)))
        self.__table = [[] for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i].append(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].append(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return []
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl + vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, i)
        st.update(r, i)

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(l))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log2(N)))
        self.__table = [[] for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i].append(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].append(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return []
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl + vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, i)
        st.update(r, i)

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(l))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()