Problem:

Priority Queue

  Priority queue is a container of elements which the element with the highest priority should be extracted first.

  For $n$ priority queues $Q_i$ ($i = 0, 1, ..., n-1$) of integers, perform a sequence of the following operations.

  
insert($t$, $x$): Insert $x$ to $Q_t$.

  
getMax($t$): Report the maximum value in $Q_t$. If $Q_t$ is empty, do nothing.

  
deleteMax($t$): Delete the maximum element from $Q_t$. If $Q_t$ is empty, do nothing.

In the initial state, all queues are empty.

Input

  The input is given in the following format.

$n \; q$
$query_1$
$query_2$
:
$query_q$

Each query $query_i$ is given by

0 $t$ $x$

or

1 $t$

or

2 $t$

  where  the first digits 0, 1 and 2 represent insert, getMax and deleteMax operations respectively.

Output

  For each getMax operation, print an integer in a line.

Constraints

  
$1 \leq n \leq 1,000$

  
$1 \leq q \leq 200,000$

  
$-1,000,000,000 \leq x \leq 1,000,000,000$

Sample Input 1

2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1

Sample Output 1

9
3
4
8



Sample input:
2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1


Sample output:
9
3
4
8

Submission status: Wrong Answer

Solution code:

class MaxPQ:
    def __init__(self):
        self.q = []

    def insert(self, x):
        self.q.append(x)
        self.swim(len(self.q)-1)

    def get_max(self):
        if len(self.q) == 0:
            return None
        return self.q[0]

    def delete_max(self):
        if len(self.q) == 0:
            return None
        self.q[0] = self.q[-1]
        self.sink(0)

    def sink(self, i):
        c1 = (i + 1) * 2 - 1
        c2 = (i + 1) * 2
        size = len(self.q)
        if c1 >= size:
            pass
        elif c1 < size and c2 >= size:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        elif self.q[c1] > self.q[c2]:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        else:
            if self.q[c2] > self.q[i]:
                self.q[c2], self.q[i] = self.q[i], self.q[c2]
                self.sink(c2)

    def swim(self, i):
        p = (i+1) // 2 - 1
        if p >= 0:
            if self.q[p] < self.q[i]:
                self.q[p], self.q[i] = self.q[i], self.q[p]
                self.swim(p)


def run():
    n, q = [int(x) for x in input().split()]
    pqs = [MaxPQ() for _ in range(n)]

    for _ in range(q):
        com = [int(x) for x in input().split()]
        c = com[0]
        if c == 0:
            t, v = com[1:]
            pqs[t].insert(v)
        elif c == 1:
            t = com[1]
            print(pqs[t].get_max())
        elif c == 2:
            t = com[1]
            pqs[t].delete_max()
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:

class MaxPQ:
    def __init__(self):
        self.q = []

    def insert(self, x):
        self.q.append(x)
        self.swim(len(self.q)-1)

    def get_max(self):
        if len(self.q) > 0:
            return self.q[0]
        else:
            return None

    def delete_max(self):
        if len(self.q) > 1:
            val = self.q.pop()
            self.q[0] = val
            self.sink(0)

    def sink(self, i):
        c1 = (i + 1) * 2 - 1
        c2 = (i + 1) * 2
        size = len(self.q)
        if c1 >= size:
            pass
        elif c1 < size and c2 >= size:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        elif self.q[c1] > self.q[c2]:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        else:
            if self.q[c2] > self.q[i]:
                self.q[c2], self.q[i] = self.q[i], self.q[c2]
                self.sink(c2)

    def swim(self, i):
        p = (i+1) // 2 - 1
        if p >= 0:
            if self.q[p] < self.q[i]:
                self.q[p], self.q[i] = self.q[i], self.q[p]
                self.swim(p)


def run():
    n, q = [int(x) for x in input().split()]
    pqs = [MaxPQ() for _ in range(n)]

    for _ in range(q):
        com = [int(x) for x in input().split()]
        c = com[0]
        if c == 0:
            t, v = com[1:]
            pqs[t].insert(v)
        elif c == 1:
            t = com[1]
            print(pqs[t].get_max())
        elif c == 2:
            t = com[1]
            pqs[t].delete_max()
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:


class MaxPQ:
    def __init__(self):
        self.q = []

    def insert(self, x):
        self.q.append(x)
        self.swim(len(self.q)-1)

    def get_max(self):
        if len(self.q) > 0:
            return self.q[0]
        else:
            return None

    def delete_max(self):
        if len(self.q) > 1:
            val = self.q.pop()
            self.q[0] = val
            self.sink(0)

    def sink(self, i):
        c1 = (i + 1) * 2 - 1
        c2 = (i + 1) * 2
        size = len(self.q)
        if c1 >= size:
            pass
        elif c1 < size and c2 >= size:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        elif self.q[c1] > self.q[c2]:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        else:
            if self.q[c2] > self.q[i]:
                self.q[c2], self.q[i] = self.q[i], self.q[c2]
                self.sink(c2)

    def swim(self, i):
        p = (i+1) // 2 - 1
        if p >= 0:
            if self.q[p] < self.q[i]:
                self.q[p], self.q[i] = self.q[i], self.q[p]
                self.swim(p)


def run():
    n, q = [int(x) for x in input().split()]
    pqs = [MaxPQ() for _ in range(n)]

    for _ in range(q):
        com = [int(x) for x in input().split()]
        c = com[0]
        if c == 0:
            t, v = com[1:]
            pqs[t].insert(v)
        elif c == 1:
            t = com[1]
            val = pqs[t].get_max()
            if val is not None:
                print(val)
        elif c == 2:
            t = com[1]
            pqs[t].delete_max()
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        a[c[1]].append(c[2])
        a[c[1]].sort()
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[-1]])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j] < c[2]:
                        a[c[1]].insert(j, c[2])
                        break
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j-1] < c[2]:
                        a[c[1]].insert(j, c[2])
                        break
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j] < c[2]:
                        a[c[1]].insert(j+1, c[2])
                        break
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Wrong Answer

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

    def insert_left(self, insert):
        if self.left is None:
            self.left = binaryTree(insert)

        else:
            t = binaryTree(insert)
            t.left = self.left
            self.left = t

    def insert_right(self, insert):
        if self.right is None:
            self.right = binaryTree(insert)

        else:
            t = binaryTree(insert)
            t.right = self.left
            self.right = t

    def put_root(self, obj):
        self.value = obj

def makeBntr(bnary, num):
    if bnary is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    #print("maxLeaf>>", bnary.value, bnary.left, bnary.right)
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        #print(bnary)
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    #print("mkBntr>>", bnary.value, bnary.left, bnary.right, num)
    if bnary is None:
        return num

    elif bnary.value is None:
        return num

    elif bnary.value < num.value:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left) 
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    ##print("n = %d, q = %d" %(n, q))
    S = [binaryTree() for i in range(n)]

    for i in range(q):
        query = input().split()
        bnary = S[int(query[1])]
        ##print('---', query[0], query[1])
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                #print("========")
                S[int(query[1])] = delLeaf(bnary)

Submission status: Wrong Answer

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    if bnary is None:
        bnary = binaryTree()
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]
    count = 1
    for i in range(q):
        query = input().split()
        if query[1] != "12":
            continue
        count += 1

        bnary = S[int(query[1])]
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

a = [int(i) for i in input().split()]
q = deque([])
for i in range(a[0]): q.append(deque([]))

for i in range(a[1]):
    cmd = [int(i) for i in input().split()]

    if cmd[0] == 0:
        q[cmd[1]].append(cmd[2])

    elif cmd[0] == 1:
        if q[cmd[1]] != deque([]):
            print(max(q[cmd[1]]))

    elif cmd[0] == 2:
        if q[cmd[1]] != deque([]):
            q[cmd[1]].remove(max(q[cmd[1]]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

a = [int(i) for i in input().split()]
ls = []
for i in range(a[0]): ls.append([])

for i in range(a[1]):
    cmd = [int(i) for i in input().split()]

    if cmd[0] == 0:
        ls[cmd[1]].append(cmd[2])
        heapq._heapify_max(ls[cmd[1]])

    elif cmd[0] == 1:
        if ls[cmd[1]] != []:
            print(ls[cmd[1]][0])

    elif cmd[0] == 2:
        if ls[cmd[1]] != []:
            ls[cmd[1]].pop(0)
            heapq._heapify_max(ls[cmd[1]])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(max(a[c[1]]))
    else:
        if a[c[1]]:
            m = max(a[c[1]])
            a[c[1]].remove(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        a[c[1]].append(c[2])
        a[c[1]].sort()
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j] < c[2]:
                        a[c[1]].insert(j+1, c[2])
                        break
                else:
                    a[c[1]].insert(0, c[2])
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j] < c[2]:
                        a[c[1]].insert(j+1, c[2])
                        break
                else:
                    a[c[1]].appendleft(c[2])
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])
                while right - left > 1:
                    mid = (right - left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])-1
                while right - left > 1:
                    mid = (right - left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])-1
                while right - left > 1:
                    mid = (right + left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify

if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [[] for i in range(n)]

    for i in range(q):
        query = input().split()

        if query[0] == '0':
            St = S[int(query[1])]
            #print(type(St), St, query[1])
            heappush(St, int(query[2]))
            #print(St, heapify(St))
            S[int(query[1])] = sorted(St)
            #print(S)

        else:
            if len(S[int(query[1])]) == 0:
                pass
            elif query[0] == '1':
                print(S[int(query[1])][-1])
            else:
                S[int(query[1])].pop()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    if bnary is None:
        bnary = binaryTree()
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]
    for i in range(q):
        query = input().split()

        bnary = S[int(query[1])]
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, q = list(map(int, input().split(' ')))
pqueues = [[] for i in range(n)]

for i in range(q):
    op = list(map(int, input().split(' ')))
    if op[0] == 0:
        heappush(pqueues[op[1]], -op[2])
    elif op[0] == 1:
        if len(pqueues[op[1]]) != 0:
            print(-1*pqueues[op[1]][0])
    elif op[0] == 2:
        if len(pqueues[op[1]]) != 0:
            heappop(pqueues[op[1]])

Submission status: Accepted

Solution code:


class MaxPQ:
    def __init__(self):
        self.q = []

    def insert(self, x):
        self.q.append(x)
        self.swim(len(self.q)-1)

    def get_max(self):
        if len(self.q) > 0:
            return self.q[0]
        else:
            return None

    def delete_max(self):
        if len(self.q) == 0:
            return

        val = self.q.pop()
        if len(self.q) > 0:
            self.q[0] = val
            self.sink(0)

    def sink(self, i):
        c1 = (i + 1) * 2 - 1
        c2 = (i + 1) * 2
        size = len(self.q)
        if c1 >= size:
            pass
        elif c1 < size and c2 >= size:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        elif self.q[c1] > self.q[c2]:
            if self.q[c1] > self.q[i]:
                self.q[c1], self.q[i] = self.q[i], self.q[c1]
                self.sink(c1)
        else:
            if self.q[c2] > self.q[i]:
                self.q[c2], self.q[i] = self.q[i], self.q[c2]
                self.sink(c2)

    def swim(self, i):
        p = (i+1) // 2 - 1
        if p >= 0:
            if self.q[p] < self.q[i]:
                self.q[p], self.q[i] = self.q[i], self.q[p]
                self.swim(p)


def run():
    n, q = [int(x) for x in input().split()]
    pqs = [MaxPQ() for _ in range(n)]

    for _ in range(q):
        com = [int(x) for x in input().split()]
        c = com[0]
        if c == 0:
            t, v = com[1:]
            pqs[t].insert(v)
        elif c == 1:
            t = com[1]
            val = pqs[t].get_max()
            if val is not None:
                print(val)
        elif c == 2:
            t = com[1]
            pqs[t].delete_max()
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# coding=utf-8
import bisect


if __name__ == '__main__':
    N, Q = map(int, input().split())
    Que = [[] for i in range(N)]

    for j in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bisect.insort_left(Que[query[1]], query[2])
        elif query[0] == 1:
            if Que[query[1]]:
                print(Que[query[1]][-1])
        elif query[0] == 2:
            if Que[query[1]]:
                Que[query[1]].pop()

Submission status: Accepted

Solution code:
# AOJ ITP2_2_C: Priority Queue
# Python3 2018.6.24 bal4u

import heapq
n, q = map(int, input().split())
Q = [[] for i in range(n)]
for i in range(q):
	a = input().split()
	t = int(a[1])
	if   a[0] == '0': heapq.heappush(Q[t], -int(a[2]))       # insert
	elif a[0] == '1' and Q[t]: print(-Q[t][0])      # getMax
	elif a[0] == '2' and Q[t]: heapq.heappop(Q[t])  # deleteMax

Submission status: Accepted

Solution code:
import heapq
n, q = map(int, input().split())
A = [ [] for i in range(n)]
for i in range(q):
    tmp = list(map(int, input().split()))
    if tmp[0] == 0:
        heapq.heappush(A[tmp[1]], -tmp[2])
    elif tmp[0] == 1 and A[tmp[1]]:
        print(-A[tmp[1]][0])
    elif tmp[0] == 2 and A[tmp[1]]:
        heapq.heappop(A[tmp[1]])

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys
import heapq

n, q = map(int, sys.stdin.readline().split())
a = [[] for i in range(n)]

for i in range(q):
    g = list(map(int, sys.stdin.readline().split()))
    if g[0] == 0:
        heapq.heappush(a[g[1]], -g[2])
    elif g[0] == 1:
        a[g[1]] and print(-a[g[1]][0])
    else:
        a[g[1]] and heapq.heappop(a[g[1]])

Submission status: Accepted

Solution code:
class MaxHeapInt(object):
    def __init__(self, val):  self.val = val
    def __lt__(self, other): return self.val > other.val
    def __eq__(self, other): return self.val == other.val
    def __str__(self): return str(self.val)


def resolve():
    import heapq
    n, Q = [int(i) for i in input().split()]
    ans = [[] for _ in range(n)]
    for _ in range(Q):
        q = [int(i) for i in input().split()]
        if q[0] == 0:
            heapq.heappush(ans[q[1]], MaxHeapInt(q[2]))
        elif q[0] == 1:
            if len(ans[q[1]]) > 0:
                print(ans[q[1]][0].val)
        else:
            if len(ans[q[1]]) > 0:
                heapq.heappop(ans[q[1]])


resolve()

Submission status: Accepted

Solution code:
import heapq

def insert(t, x):
    global Qlist
    heapq.heappush(Qlist[t], -x)

def getMax(t):
    global Qlist
    if Qlist[t]:
        num = Qlist[t][0]
        print(-num)

def deleteMax(t):
    global Qlist
    if Qlist[t]:
        heapq.heappop(Qlist[t])


Qlist = []
n,q  = map(int, input().split())

for i in range(n):
    Qi = []
    heapq.heapify(Qi)
    Qlist.append(Qi)

for i in range(q):
    queryi = list(map(int, input().split()))

    if queryi[0] == 0:
        insert(queryi[1], queryi[2])
    
    elif queryi[0] == 1:
        getMax(queryi[1])

    else:
        deleteMax(queryi[1])

Submission status: Accepted

Solution code:

from sys import stdin
import heapq

n,q = map(int,input().split())
q_list = [list() for i in range(n)]

for i in range(q):
    l = list(map(int,stdin.readline().split()))
    if l[0] == 0:
        heapq.heappush(q_list[l[1]],-l[2])
    elif l[0] == 1:
        if q_list[l[1]]:
            print(-q_list[l[1]][0])
    elif q_list[l[1]]:
        heapq.heappop(q_list[l[1]])

Submission status: Accepted

Solution code:
import heapq
n,q = map(int,input().split())

S = [[] for i in range(n)]
for i in range(q):
    query = tuple(map(int,input().split()))

    if query[0] == 0:
        heapq.heappush(S[query[1]],-1*query[2])
    elif query[0] == 1:
        if len(S[query[1]]) != 0:
            a = heapq.heappop(S[query[1]])
            print(-1*a)
            heapq.heappush(S[query[1]],a)
    else:
        if len(S[query[1]]) != 0:
            heapq.heappop(S[query[1]])

Submission status: Accepted

Solution code:
import heapq as hq
n, q = map(int, input().split())
queues = [[] for i in range(n)]
while q:
    q -= 1
    s = [*map(int, input().split())]
    if s[0] == 0:
        hq.heappush(queues[s[1]], -s[2])
    elif s[0] == 1 and queues[s[1]]:
        print(-queues[s[1]][0])
    elif queues[s[1]]:
        hq.heappop(queues[s[1]])

Submission status: Accepted

Solution code:
import heapq
n,q = map(int,input().split())
Q = [[] for i in range(n)]
for i in range(q):
    a = input().split()
    t = int(a[1])
    if a[0] == "0":heapq.heappush(Q[t],-int(a[2]))
    elif a[0] == "1" and Q[t]: print(-Q[t][0])
    elif a[0] == "2" and Q[t]: heapq.heappop(Q[t])

Submission status: Accepted

Solution code:
import heapq

def main():
    n,m = map(int,input().split())
    pq = [[] for _ in range(n)]
    for i in range(n):heapq.heapify(pq[i])
    for _ in range(m):
        q = input().split()
        if   q[0] == '0'  :heapq.heappush(pq[int(q[1])],-int(q[2]))
        elif pq[int(q[1])]:
            if q[0] == '1'  :print (-pq[(int(q[1]))][0])
            else            :heapq.heappop(pq[int(q[1])])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

n, q = map(int, input().split())
Q = [[] for i in range(n)]
for i in range(q):
    x, *y = map(int, input().split())
    if x == 0:
        heapq.heappush(Q[y[0]], -y[1])
    elif x == 1 and Q[y[0]]:
        print(-Q[y[0]][0])
    elif x == 2 and Q[y[0]]:
        heapq.heappop(Q[y[0]])

Submission status: Accepted

Solution code:
import heapq
from collections import deque

n, q = list(map(int, input().split()))
Q = []
[Q.append([]) for _ in range(n)]

for i in range(q):
    query = list(map(int, input().split()))
    t = query[1]

    # insert
    if query[0] == 0:
        heapq.heappush(Q[t], -query[2])

    # getMax
    elif query[0] == 1:
        if Q[t]:
            print(-Q[t][0])

    # deleteMax
    else:
        if Q[t]:
            heapq.heappop(Q[t])