Kirill and Mushrooms (Codeforces 1945F)
Tags: Others, sortings

As soon as everyone in the camp fell asleep, Kirill sneaked out of the tent and went to the Wise Oak to gather mushrooms.It is known that there are $$$n$$$ mushrooms growing under the Oak, each of which has magic power $$$v_i$$$. Kirill really wants to make a magical elixir of maximum strength from the mushrooms.The strength of the elixir is equal to the product of the number of mushrooms in it and the minimum magic power among these mushrooms. To prepare the elixir, Kirill will sequentially pick one mushroom growing under the Oak. Kirill can gather mushrooms in any order.However, it's not that simple. The Wise Oak informed Kirill of a permutation of numbers $$$p$$$ from $$$1$$$ to $$$n$$$. If Kirill picks only $$$k$$$ mushrooms, then the magic power of all mushrooms with indices $$$p_1, p_2, \dots, p_{k - 1}$$$ will become $$$0$$$. Kirill will not use mushrooms with zero magic power to prepare the elixir.Your task is to help Kirill gather mushrooms in such a way that he can brew the elixir of maximum possible strength. However, Kirill is a little scared to stay near the oak for too long, so out of all the suitable options for gathering mushrooms, he asks you to find the one with the minimum number of mushrooms.A permutation of length $$$n$$$ is an array consisting of $$$n$$$ different integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears in the array twice) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ appears in the array).

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of mushrooms.The second line contains an array $$$v$$$ of size $$$n$$$ ($$$1\le v_i \le 10^9$$$) — the magic powers of the mushrooms.The third line contains a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$.It is guaranteed that the sum of the values of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output two integers separated by a space — the maximum strength of the elixir that can be brewed and the minimum number of mushrooms that Kirill needs to use for this.

Note: In the first example, you need to take the mushrooms with indices $$$1$$$ and $$$2$$$, so the strength of the elixir is equal to $$$2 \cdot \min(a_1, a_2) = 2 \cdot \min(9, 8) = 2 \cdot 8 = 16$$$. Note that the magic power of the mushroom with index $$$3$$$ after picking two mushrooms will become $$$0$$$.

Sample Inputs:
6
3
9 8 14
3 2 1
5
1 2 3 4 5
1 2 3 4 5
6
1 2 3 4 5 6
6 5 4 3 2 1
5
1 4 6 10 10
2 1 4 5 3
4
2 2 5 5
4 2 3 1
5
1 2 9 10 10
1 4 2 3 5

Sample Outputs:
16 2
9 3
8 2
20 2
5 1
20 2

Solution (Python):
import heapq
import math
t = int(input())
for i in range(t):
    n = int(input())
    v = list(map(int, input().split()))
    p = list(map(int, input().split()))
    max_size = (n + 2) // 2
    h = []
    heapq.heapify(h)
    for j in range(max_size):
        heapq.heappush(h, v[p[n - 1 - j] - 1])
    if n % 2 == 0:
        heapq.heappop(h)
    output = (len(h) * h[0], len(h))
    while True:
        if len(h) == 1:
            if h[0] >= output[0]:
                output = (h[0], 1)
            break
        else:
            heapq.heappop(h)
            l = len(h)
            if h[0] < v[p[l - 1] - 1]:
                heapq.heappop(h)
                heapq.heappush(h, v[p[l - 1] - 1])
            if h[0] * l >= output[0]:
                output = (h[0] * l, l)
    print(output[0], output[1])

Solution (Python):
from heapq import heappop, heappush
for _ in range(int(input())):
    x = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    ans = 0
    p = -1
    for i in range(x - 1, -1, -1):
        heappush(h, a[b[i] - 1])
        while len(h) > i + 1:
            heappop(h)
        r = h[0] * len(h)
        if r >= ans:
            ans = r
            p = i + 1
    print(ans, p)

Solution (Python):
import math

def ip():
    return input()

def ip_int():
    return int(input())

def ip_arr():
    return list(input().split())

def ip_int_arr():
    return list(map(int, input().split()))

def ip_int_tuple():
    return map(int, input().split())

def ip_tuple():
    return input().split()
import math
from heapq import *

def solve():
    n = ip_int()
    v = ip_int_arr()
    p = ip_int_arr()
    min_heap = []
    ans = 0
    ans_len = int(1000000000.0)
    for i in reversed(range(n)):
        p[i] -= 1
        heappush(min_heap, v[p[i]])
        cur_len = min(i + 1, len(min_heap))
        while len(min_heap) > cur_len:
            heappop(min_heap)
        cur_ans = cur_len * min_heap[0]
        if cur_ans > ans:
            ans = cur_ans
            ans_len = cur_len
        elif cur_ans == ans and cur_len < ans_len:
            ans = cur_ans
            ans_len = cur_len
    print(ans, ans_len)
t = ip_int()
for _ in range(t):
    solve()