Problem: There is a function f(x), which is initially a constant function f(x) = 0.  We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:    * An update query `1 a b`: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x).   * An evaluation query `2`: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.  We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.

Submission attempts (in order):
#!/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):

for query in qs:
    print(1, 1)
    
    
    #     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_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)

#!/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):

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)

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

# class Node(object):

#         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)
#

#         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)
#

#         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

#
#         else:
#             left = nearest.value
#             current = nearest
#             while True:
#                 if not current.isright:
#                     break
#                 else:
#                     current = current.parent
#             right = current.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):

for query in qs:
    if query[0] == 1:
        pass
    else:
        print(1, 1)
    
    
    #     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_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)

#!/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)


Verdicts: Runtime Error

Runtime Error

Wrong Answer

Accepted