Pk8CN7Zb

1from sys import stdin
2from collections import defaultdict as dd
3
4class Node: 
5  
6    # Constructor to create a new node 
7    def __init__(self, key): 
8        self.key = key  
9        self.left = None
10        self.right = None
11  
12# A utility function to insert a new node with given key in BST 
13def insert( node, key): 
14  
15    # If the tree is empty, return a new node 
16    if node is None: 
17        return Node(key) 
18  
19    # Otherwise recur down the tree 
20    if key < node.key: 
21        node.left = insert(node.left, key) 
22    else: 
23        node.right = insert(node.right, key) 
24  
25    # return the (unchanged) node pointer 
26    return node 
27  
28
29def minValueNode( node): 
30    current = node 
31  
32    # loop down to find the leftmost leaf 
33    while(current.left is not None): 
34        current = current.left  
35  
36    return current  
37  
38# Given a binary search tree and a key, this function 
39# delete the key and returns the new root 
40def deleteNode(root, key): 
41  
42    # Base Case 
43    if root is None: 
44        return root  
45  
46    # If the key to be deleted is smaller than the root's 
47    # key then it lies in  left subtree 
48    if key < root.key: 
49        root.left = deleteNode(root.left, key) 
50  
51    # If the kye to be delete is greater than the root's key 
52    # then it lies in right subtree 
53    elif(key > root.key): 
54        root.right = deleteNode(root.right, key) 
55  
56    # If key is same as root's key, then this is the node 
57    # to be deleted 
58    else: 
59          
60        # Node with only one child or no child 
61        if root.left is None : 
62            temp = root.right  
63            root = None 
64            return temp  
65              
66        elif root.right is None : 
67            temp = root.left  
68            root = None
69            return temp 
70  
71        # Node with two children: Get the inorder successor 
72        # (smallest in the right subtree) 
73        temp = minValueNode(root.right) 
74  
75        # Copy the inorder successor's content to this node 
76        root.key = temp.key 
77  
78        # Delete the inorder successor 
79        root.right = deleteNode(root.right , temp.key) 
80  
81  
82    return root
83
84############################### ABOVE ONLY BST IMPLEMENTATION ########################
85# The BST stores the maximum rating of each KG. We update the BST, if the maximum rating changes for any KG. 
86
87n, q = map(int, stdin.readline().split())
88
89# set of infants belonging to each KG
90kinder = dd(set) 
91
92# the maximum rate of a KG
93kindermaxrate = dd(int)
94
95# The KG infant i belongs to is infant[i]
96infant = [0]*(n+1)
97
98# The rating of infant i is rating[i]
99rating = [0]*(n+1)
100
101# root of BST, I had to follow the API of copy pasted code.
102root = None
103
104# Get the initial arrangement of infants and KGs
105for i in range(n):
106    a, b = map(int, stdin.readline().split())
107
108    # to KG b and infant a.
109    kinder[b].add(i+1)
110
111    # location of infant
112    infant[i+1] = b 
113    # rating of infant
114    rating[i+1] = a # can be a list
115
116    # get the maximum rating in KG
117    t = kindermaxrate[b]
118
119    # if max rating is 0, i.e., empty KG. If > 0, it has elements.
120    if t > 0:
121        # if new infant rating is higher than current max
122        if a > t:
123            # update max for that KG
124            kindermaxrate[b] = a
125            # insert new max
126            root = insert(root, t)
127            # delete previous max
128            root = deleteNode(root, a)
129        # if lower than current max
130        else:
131            pass
132    else:
133        # add new max rating for the KG and add this max rating to BST
134        kindermaxrate[b] = a
135        root = insert(root, kindermaxrate[b])
136
137for _ in range(q):
138    c, d = map(int, stdin.readline().split())
139    # remove from current KG
140    curr = infant[c]
141    kinder[curr].remove(c)
142
143    # if transferred infant is the maximum rated infant of current, update max rating and BST because of this removal from curr.
144    if kindermaxrate[curr] == rating[c]:
145        if len(kinder[curr]) > 0:
146            mx = max((rating[i] for i in kinder[curr]))
147            kindermaxrate[curr] = mx
148            root = deleteNode(root, rating[c]) 
149            root = insert(root, mx) 
150        else:
151            root = deleteNode(root, rating[c])
152            kindermaxrate[curr] = -1
153
154    else:
155        pass
156        
157    # add to new KG D
158    infant[c] = d
159    kinder[d].add(c)
160
161    # update max rating and update bst because of this addition to D.
162    t = kindermaxrate[d]
163    if rating[c]>t:
164        if t!=0:
165            root = deleteNode(root, t) 
166        root = insert(root, rating[c])
167        kindermaxrate[d] = rating[c]
168    else:
169        pass
170
171    print(minValueNode(root).key)