The executive chef is trying to bring some competitive spirit into his kitchen. He wants to split the chefs into two teams based on their age - he'll form the young and the old team. To make it fair, he will split them evenly or give the young team one person advantage when there is an odd number of chefs. Ages of all employees are unique. The executive chef also rated all chefs according to their cooking skills. Rating of a team is equal to the sum of ratings of its members. The chefs have developed a habit of coming to work late. The executive chef wants to keep the teams as fair as possible at all times and is therefore forced to change the teams each time one of the chefs comes to work in the morning. He needs your help with this task.

------ Input ------ 

The first line contains the number of chefs N. The following N lines describe the chefs in order as they come to work. Each chef is described by two integers, his or her age A_{i} and rating R_{i}.

------ Output ------ 

Every time a new chef joins the kitchen, output the absolute difference between team ratings.

------ Constraints ------ 

$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$1 ≤ R_{i} ≤ 1000$

----- Sample Input 1 ------ 
5
2 3
1 7
5 5
3 1
8 15
----- Sample Output 1 ------ 
3
4
5
4
9

Source: codechef | Difficulty: MEDIUM
Tags: Data structures

Implementation

Ad-hoc


Solutions:
from bisect import *
from math import *

def main():
	chefnb = int(input())
	chefList = list()
	diff = 0
	for i in range(chefnb):
		inp = input()
		(age, val) = inp.split(' ')
		chef = (int(age), int(val))
		index = bisect(chefList, chef)
		chefList.insert(index, chef)
		mid = ceil(len(chefList) / 2.0)
		if index < mid:
			diff -= int(val)
			if len(chefList) % 2 == 0:
				diff += chefList[mid][1] * 2
		else:
			diff += int(val)
			if len(chefList) % 2 == 1:
				diff -= chefList[mid - 1][1] * 2
		print(abs(diff))
main()


import heapq
n = int(input())
young = []
youngrate = 0
old = []
oldrate = 0
age_to_rating = {}
for i in range(n):
	(age, rating) = map(int, input().split())
	age_to_rating[age] = rating
	if len(young) == 0 or age < -young[0]:
		heapq.heappush(young, -age)
		youngrate += rating
	else:
		heapq.heappush(old, age)
		oldrate += rating
	if len(young) > len(old) + 1:
		oldestyoung = -1 * heapq.heappop(young)
		youngrate -= age_to_rating[oldestyoung]
		heapq.heappush(old, oldestyoung)
		oldrate += age_to_rating[oldestyoung]
	elif len(old) > len(young):
		youngestold = heapq.heappop(old)
		oldrate -= age_to_rating[youngestold]
		heapq.heappush(young, -youngestold)
		youngrate += age_to_rating[youngestold]
	print(abs(oldrate - youngrate))


from heapq import *
n = int(input())
young = []
old = []
c = 0
d = {}
for i in range(1, n + 1):
	(a, r) = map(int, input().split())
	try:
		d[a].append(r)
	except:
		d[a] = [r]
	if i % 2 == 1:
		if len(old) == 0 or a < old[0]:
			heappush(young, -a)
			c += r
		else:
			heappush(old, a)
			x = heappop(old)
			c += 2 * d[x][0]
			c -= r
			heappush(young, -x)
	elif a >= -young[0]:
		c -= r
		heappush(old, a)
	else:
		x = -heappop(young)
		heappush(young, -a)
		c += r
		c -= 2 * d[x][0]
		heappush(old, x)
	print(abs(c))


import collections as clts
import math
import heapq

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)

def take_input(type='int'):
	if type == 'int':
		return int(input())
	elif type == 'str':
		return input()
	elif type == 'list-int':
		return list(map(int, input().split()))
	elif type == 'list-float':
		return list(map(float, input().split()))
	else:
		return None
N = int(input())
maxYoung = math.ceil(N / 2)
maxOld = N - maxYoung
(youngRat, oldRat) = (0, 0)
(young, old) = ([], [])
for i in range(N):
	(A, R) = take_input('list-int')
	if i % 2 == 0:
		if len(young) == 0:
			heapq.heappush(young, (-A, R))
			youngRat += R
		elif A > -young[0][0] and A < old[0][0] or A < -young[0][0]:
			heapq.heappush(young, (-A, R))
			youngRat += R
		elif A > old[0][0]:
			(oldA, oldR) = heapq.heappop(old)
			heapq.heappush(young, (-oldA, oldR))
			heapq.heappush(old, (A, R))
			oldRat += R - oldR
			youngRat += oldR
	elif len(old) == 0:
		if A > -young[0][0]:
			heapq.heappush(old, (A, R))
			oldRat += R
		elif A < -young[0][0]:
			(youngA, youngR) = heapq.heappop(young)
			heapq.heappush(young, (-A, R))
			heapq.heappush(old, (-youngA, youngR))
			oldRat += youngR
			youngRat += R - youngR
	elif A > old[0][0] or (A < old[0][0] and A > -young[0][0]):
		heapq.heappush(old, (A, R))
		oldRat += R
	elif A < -young[0][0]:
		(youngA, youngR) = heapq.heappop(young)
		heapq.heappush(young, (-A, R))
		heapq.heappush(old, (-youngA, youngR))
		oldRat += youngR
		youngRat += R - youngR
	print(abs(youngRat - oldRat))


from bisect import *
from math import *
chefList = list()
diff = 0
for _ in range(int(input())):
	(age, value) = map(int, input().split(' '))
	chef = (age, value)
	index = bisect(chefList, chef)
	chefList.insert(index, chef)
	mid = ceil(len(chefList) / 2)
	if index < mid:
		diff -= value
		if len(chefList) % 2 == 0:
			diff += chefList[mid][1] * 2
	else:
		diff += value
		if len(chefList) % 2 == 1:
			diff -= chefList[mid - 1][1] * 2
	print(abs(diff))


from heapq import *
young = []
old = []
heapify(young)
heapify(old)
y_rating = 0
o_rating = 0
N = int(input())
element = tuple(map(int, input().split()))
element = (-element[0], element[1])
heappush(young, element)
y_rating += element[1]
print(y_rating)
for i in range(1, N):
	element = tuple(map(int, input().split()))
	if i % 2 == 1:
		if element[0] < -young[0][0]:
			element = (-element[0], element[1])
			a = heappushpop(young, element)
			y_rating = y_rating + element[1] - a[1]
			o_rating += a[1]
			a = (-a[0], a[1])
			heappush(old, a)
		else:
			o_rating += element[1]
			heappush(old, element)
	elif element[0] < -young[0][0]:
		y_rating += element[1]
		element = (-element[0], element[1])
		heappush(young, element)
	else:
		a = heappushpop(old, element)
		o_rating = o_rating + element[1] - a[1]
		y_rating = y_rating + a[1]
		a = (-a[0], a[1])
		heappush(young, a)
	if y_rating > o_rating:
		print(y_rating - o_rating)
	else:
		print(o_rating - y_rating)