Problem p03040 (python)

Fixed submission:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import heapq

INF = 10 ** 10

Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]

left = []
right = []
a_s = []
current_median = None
heapq.heappush(left, INF)
heapq.heappush(right, INF)
a_current = 0
for query in qs:
    if query[0] == 1:
        _, a, b = query
        a_s.append(a)
        b_all += b

        last_left, last_right = -left[0], right[0]
        heapq.heappush(left, -a)
        heapq.heappush(right, a)
        heapq.heappush(left, -heapq.heappop(right))
        heapq.heappush(right, -heapq.heappop(left))
        current_median = -left[0]
        if last_left <= a and a <= last_right:
            pass
        else:
            # a_current += abs(left[0] + right[0])
            a_current += min(abs(last_right - a), abs(last_left - a))
    else:
        print(current_median, a_current+b_all)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    if query[0] == 1:
        _, a, b = query
        b_all += b
        if tree is None:
            tree = Node(a)
        else:
            tree.add_node(Node(a))
        sum_value += a
        k_value += 1
    else:
        weight = sum_value / k_value
        l, r = tree.find_lr_value(weight)
        targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
        targets_values = [(target, tree.calc(target) + b_all) for target in targets]
        x,value = min(targets_values, key=lambda x: (x[1], x[0]))
        print(x, value)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right: Node = None
        self.parent: Node = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    print(1, 1)
    # if query[0] == 1:
    #     _, a, b = query
    #     b_all += b
    #     if tree is None:
    #         tree = Node(a)
    #     else:
    #         tree.add_node(Node(a))
    #     sum_value += a
    #     k_value += 1
    # else:
    #     weight = sum_value / k_value
    #     l, r = tree.find_lr_value(weight)
    #     targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
    #     targets_values = [(target, tree.calc(target) + b_all) for target in targets]
    #     x,value = min(targets_values, key=lambda x: (x[1], x[0]))
    #     print(x, value)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right: Node = None
        self.parent: Node = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    if query[0] == 1:
        _, a, b = query
        b_all += b
        if tree is None:
            tree = Node(a)
        else:
            tree.add_node(Node(a))
        sum_value += a
        k_value += 1
    else:
        weight = sum_value / k_value
        l, r = tree.find_lr_value(weight)
        targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
        targets_values = [(target, tree.calc(target) + b_all) for target in targets]
        x,value = min(targets_values, key=lambda x: (x[1], x[0]))
        print(x, value)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right: Node = None
        self.parent: Node = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q-1)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    if query[0] == 1:
        _, a, b = query
        b_all += b
        if tree is None:
            tree = Node(a)
        else:
            tree.add_node(Node(a))
        sum_value += a
        k_value += 1
    else:
        weight = sum_value / k_value
        l, r = tree.find_lr_value(weight)
        targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
        targets_values = [(target, tree.calc(target) + b_all) for target in targets]
        x,value = min(targets_values, key=lambda x: (x[1], x[0]))
        print(x, value)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right: Node = None
        self.parent: Node = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    if query[0] == 1:
        _, a, b = query
        b_all += b
        if tree is None:
            tree = Node(a)
        else:
            tree.add_node(Node(a))
        sum_value += a
        k_value += 1
    else:
        weight = sum_value / k_value
        l, r = tree.find_lr_value(weight)
        targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
        targets_values = [(target, tree.calc(target) + b_all) for target in targets]
        x,value = min(targets_values, key=lambda x: (x[1], x[0]))
        print(x, value)

exit(0)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right: Node = None
        self.parent: Node = None
        self.isright = False

    def add_node(self, node):
        if node.value > self.value:
            if self.right is None:
                self.right = node
                node.parent = self
                node.isright = True
            else:
                self.right.add_node(node)
        else:
            if self.left is None:
                self.left = node
                node.parent = self
                node.isright = False
            else:
                self.left.add_node(node)

    def search_nearest_node(self, value):
        if value > self.value:
            if self.right is None:
                return self
            else:
                return self.right.search_nearest_node(value)
        else:
            if self.left is None:
                return self
            else:
                return self.left.search_nearest_node(value)

    def find_lr_value(self, value):
        nearest = self.search_nearest_node(value)
        if nearest.value > value:
            right = nearest.value
            current = nearest
            while True:
                if current.isright:
                    break
                else:
                    current = current.parent
            left = current.value
            return left, right

        else:
            left = nearest.value
            current = nearest
            while True:
                if not current.isright:
                    break
                else:
                    current = current.parent
            right = current.value
            return left, right

    def calc(self, value):
        result = abs(self.value -value)
        if self.left is not None:
            result += self.left.calc(value)
        if self.right is not None:
            result += self.right.calc(value)
        return result


Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
for _ in range(Q):
    query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
    if query[0] == 1:
        _, a, b = query
        b_all += b
        if tree is None:
            tree = Node(a)
        else:
            tree.add_node(Node(a))
        sum_value += a
        k_value += 1
    else:
        weight = sum_value / k_value
        l, r = tree.find_lr_value(weight)
        targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
        targets_values = [(target, tree.calc(target) + b_all) for target in targets]
        x,value = min(targets_values, key=lambda x: (x[1], x[0]))
        print(x, value)

exit(0)