We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $$$k$$$. The answer will be $$$YES$$$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $$$NO$$$.

Time Complexity: $$$(O(q * log(n)))$$$ where $$$q$$$ is number of queries and $$$n$$$ is number of friends Space Complexity: $$$O(n)$$$

from heapq import heappop, heappush
from collections import defaultdict

def main():
    n, k, q = map(int, input().split())
    friendship = list(map(int, input().split()))
    hashMap = defaultdict(int)
    heap = []

    for _ in range(q):
        type, friend = map(int, input().split())
        if type == 1:
            hashMap[friend] = 2
            heappush(heap, (friendship[friend - 1], friend))
        else:
            if hashMap[friend]:
                while len(heap) > k:
                    weight, f = heappop(heap)
                    hashMap[f] = 1 
            if hashMap[friend] == 2:
                print('YES') 
            else:
                print('NO')
    
if __name__ == '__main__':
    main()
 
 

The order in which they will be applied is not important.

To solve it, it should be noted that despite the way the deck with bonuses works, the order in which they will be applied is not important. Then, when we meet the hero card, we just need to add to the answer the maximum of the available bonuses.

Constraints make you use data structures such as $$$heap$$$ to quickly find and extract the maximum.

Total complexity: $$$O(nlogn)$$$

import sys
from heapq import heappush, heappop

t = int(sys.stdin.readline().strip())

for _ in range(t):
    
    n =  int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    my_heap = []
    ans = 0
    for num in nums:
        if num:
            heappush(my_heap, -1 * num)
        else:
            if my_heap:
                ans +=( heappop(my_heap) * -1)
    print(ans)

When do we print $$$NO$$$?

If we can't form a valid topological order of the vertices by using only the directed edges, the answer is $$$NO$$$.

If the graph consisting of the vertices and only directed edges contains at least one cycle then the answer is $$$NO$$$. In other words, If we can’t form a valid topological order of the vertices with just the directed edges, we print $$$NO$$$.

Let’s now have the topological sort of the graph without undirected edges. For each pair of vertices $$$X, Y$$$ in the undirected edges, if $$$X$$$ comes before $$$Y$$$ in the topological order, we direct the edge from $$$X$$$ to $$$Y$$$, otherwise we direct it from $$$Y$$$ to $$$X$$$.

from collections import deque, defaultdict


def topSort(graph, indegree):
    queue = deque()

    for node in range(n):
        if not indegree[node]:
            queue.append(node)

    top_order = []

    while queue:
        cur = queue.popleft()
        top_order.append(cur)

        for neigh in graph[cur]:
            indegree[neigh] -= 1

            if not indegree[neigh]:
                queue.append(neigh)
    
    return top_order


t = int(input())

for _ in range(t):
    n, m = map(int, input().split())

    directed = []
    undirected = []
    
    for i in range(m):
        direction, x, y = map(int, input().split())

        x -= 1 # let's make it zero indexed
        y -= 1

        if direction:
            directed.append((x, y))
        
        else:
            undirected.append((x, y))
    

    graph = [[] for node in range(n)]
    indegree = defaultdict(int)

    for x, y in directed:
        graph[x].append(y)
        indegree[y] += 1
    

    order= topSort(graph, indegree)

    if len(order) < n:
        print("NO")
    
    else:
        # compute the index of each node in the topological order
        temp = {node: idx for idx, node in enumerate(order)}


        print('YES')
        for x, y in undirected:
            if temp[x] < temp[y]:
                print(x + 1, y + 1)
                
            else:
                print(y + 1, x + 1)

        for x, y in directed:
            print(x + 1, y + 1)