monk-and-some-queries

Monk was asked to answer some queries in an interview. He is given an empty array A. Queries are of 4 types:-
1. 1 X - Add number X to the array A.
2. 2 X - Remove a single instance of number X from the array A. If not possible, print "-1" without the quotes.
3. 3 - Find the maximum element in the array A.
4. 4 - Find the minimum element in the array A.  

Input:
The first line contains the integer Q.
The next Q lines will each contain a query like the ones mentioned above.

Output: 
For queries 3 and 4, print the answer in a new line. If the array is empty for query 3 and 4, then print "-1" without the quotes.

Constraints:
1 ≤ Q ≤ 100000
1 ≤ X ≤ 100000

SAMPLE INPUT
5
1 5
1 9
1 6
3
2 1

SAMPLE OUTPUT
9
-1

Explanation

There are 5 queries.
Query 1 - 5 is added to the array.
Query 2 - 9 is added to the array.
Query 3 - 6 is added to the array.
Query 4 - The maximum element in the array is 9.
Query 5 - Since there is no element in the array with value 1, so the output is -1.

Source: hackerearth | Difficulty: EASY
Tags: Data structures


Solutions:
import collections
import heapq

def solve(xss):
	res = []
	counts = collections.defaultdict(lambda: 0)
	min_q = []
	max_q = []
	for xs in xss:
		if xs[0] == 1:
			counts[xs[1]] += 1
			heapq.heappush(min_q, xs[1])
			heapq.heappush(max_q, -xs[1])
		elif xs[0] == 2:
			if not counts[xs[1]]: res.append(-1)
			else: counts[xs[1]] -= 1
		elif xs[0] == 3:
			while len(max_q) and not counts[-max_q[0]]: heapq.heappop(max_q)
			x = -1
			if len(max_q): x = -max_q[0]
			res.append(x)
		elif xs[0] == 4:
			while len(min_q) and not counts[min_q[0]]: heapq.heappop(min_q)
			x = -1
			if len(min_q): x = min_q[0]
			res.append(x)
	return '\n'.join(str(r) for r in res)

if __name__ == '__main__':
	xss = [list(map(int, input().split())) for _ in range(int(input()))]
	print(solve(xss))


a = []
maxa = 0
mina = 100001
for _ in range(int(input())):
	b = input().split()
	if b[0] == "1":
		x = int(b[1])
		a.append(x)
		maxa = max(maxa, x)
		mina = min(mina, x)
	elif b[0] == "2":
		x = int(b[1])
		if x in a:
			a.remove(x)
			if len(a):
				if x == maxa:
					maxa = max(a)
				elif x == mina:
					mina = min(a)
			else:
				maxa = 0
				mina = 100001
		else:
			print(-1)
	elif b[0] == "3":
		print(maxa if len(a) else -1)
	else:
		print(mina if len(a) else -1)
		


from collections import defaultdict
n=eval(input())
minn=1000001
maxx=0
a=defaultdict(int)
ans=[]
count=0
for i in range(0,n):
	x=list(map(int,input().split()))
	if x[0]==1:
		if x[1]>maxx:
			maxx=x[1]
		if x[1]<minn:
			minn=x[1]
		a[x[1]]+=1
		count+=1
	elif x[0]==2:
		if a[x[1]]>0:
			a[x[1]]-=1
			if a[x[1]]==0 and x[1]==maxx:
				k=list(a.keys())
				maxx=0
				#print k
				for j in range(0,len(k)):
					if a[k[j]]>0 and k[j]>maxx:
						maxx=k[j]
						#print maxx
			if a[x[1]]==0 and x[1]==minn:
				k=list(a.keys())
				minn=1000001
				for j in range(0,len(k)):
					if a[k[j]]>0 and k[j]<minn:
						minn=k[j]        
			count-=1
		else:
			ans.append(-1)
	elif x[0]==3:
		if count>0:
			ans.append(maxx)
		else:
			ans.append(-1)
	elif x[0]==4:
		if count>0:
			ans.append(minn)
		else:
			ans.append(-1)
#print a
#print maxx
#print minn
for i in range(0,len(ans)):
	print(ans[i])


q = eval(input())
arr = [0]*(100001)
noe = 0
mini = 10**9
maxi = -1
for _ in range(q):
	xi = input().split()
	x = int(xi[0])
	y = int(xi[-1])
	if(x==1):
		arr[y]+=1
		noe+=1
		mini = min(y,mini)
		maxi = max(y,maxi)
	elif(x==2):
		if(arr[y]==0):
			print(-1)
		else:
			arr[y]-=1
			while(mini <100001 and arr[mini]==0 ):
				mini+=1
			while( maxi > 0 and arr[maxi]==0):
				maxi-=1
			noe-=1
	elif(x==3):
		if(noe==0):
			print(-1)
		else:
			print(maxi)
	else:
		if(noe==0):
			print(-1)
		else:
			print(mini)
		


arr=[0 for _ in range(100001)]
import heapq
n=eval(input())
hepmin=[]
hepmax=[]
for _ in range(n):
	s=input()
	try:a,b=list(map(int,s.split()))
	except:a=int(s)
	if a==1:
		arr[b]+=1
		heapq.heappush(hepmin,b)
		heapq.heappush(hepmax,-b)
		
	elif a==2:
		if arr[b]==0:print(-1)
		else:
			arr[b]-=1
	elif a==3:
		if len(hepmax)==0:print(-1)
		else:
			while arr[-hepmax[0]]==0:
				heapq.heappop(hepmax)
				if len(hepmax)==0:break
			if len(hepmax)>0:print(-hepmax[0])
			else:print(-1)
			
	else:
		if len(hepmin)==0:print(-1)
		else:
			while arr[hepmin[0]]==0:
				heapq.heappop(hepmin)
				if len(hepmin)==0:break
			if len(hepmin)>0:print(hepmin[0])
			else:print(-1)
		



import heapq
MX = 10 ** 5 + 1
Q = int(input())
a, b = [], []
c = [0] * MX
n = 0
for loop in range(Q):
	q = list(map(int, input().split()))
	if   q[0] == 1:
		heapq.heappush(a, -q[1])
		heapq.heappush(b, q[1])
		c[q[1]] += 1
		n += 1
	elif q[0] == 2:
		if c[q[1]] == 0:
			print(-1)
		else:
			c[q[1]] -= 1
			n -= 1
	elif q[0] == 3:
		if n == 0:
			print(-1)
		else:
			while c[-a[0]] == 0:
				heapq.heappop(a)
			print(-a[0])
	elif q[0] == 4:
		if n == 0:
			print(-1)
		else:
			while c[b[0]] == 0:
				heapq.heappop(b)
			print(b[0])


import heapq
def heapify(pos,heap):
	left=(pos*2)+1
	right=left+1
	l=len(heap)
	#print l
	if left<l and heap[left]>heap[pos]:
		big=left
	else:
		big=pos
	if right<l and heap[right]>heap[big]:
		big=right
	if pos!=big:
		heap[pos],heap[big]=heap[big],heap[pos]
		heapify(big,heap)
def push(val,heap):
	heap.append(val)
	pos=len(heap)-1
	i=pos
	par=(pos-1)/2
	while par>=0 and heap[par]<heap[i]:
		heap[par],heap[i]=heap[i],heap[par]
		i=par
		par=(par-1)/2
def pop(heap):
	heap[0]=heap[len(heap)-1]
	del heap[len(heap)-1]
	if len(heap)>1:
		#print "Heap"
		heapify(0,heap)
n=eval(input())
minheap=[]
maxheap=[]
count=[0]*1000000
for i in range(n):
	a=list(map(int,input().split()))
	if a[0]==1:
		if count[a[1]]==0:
			push(a[1],maxheap)
			heapq.heappush(minheap,a[1])
		count[a[1]]+=1
		
	elif a[0]==2:
		if count[a[1]]==0:
			print(-1)
		else:
			count[a[1]]-=1
	elif a[0]==3:
		while len(maxheap)>0 and count[maxheap[0]]==0:
			pop(maxheap)
		if len(maxheap)>0:    
			print(maxheap[0])
		else:
			print(-1)
	elif a[0]==4:
		while len(minheap)>0 and count[minheap[0]]==0:
			heapq.heappop(minheap)
		if len(minheap)>0:
			print(minheap[0])
		else:
			print(-1)