https://www.acmicpc.net/problem/1966
initial
not that hard we append both the index and value to our queue. The index is needed cuz for repetitive values like [1,1,9,1,1], we cant just compare by the values. So we assign an incremental index and we sort the given list descending.
If the value that we popped from queue is the highest, and if the index of that value is m (mth in the original list sequence), then that is the answer.
solution
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
t= int(input())
for _ in range(t):
n,m=map(int,input().split())
lst =list(map(int,input().split()))
queue =deque()
for i,v in enumerate(lst):
queue.append((i,v))
lst.sort(reverse=True)
count=0
while queue:
i,v= queue.popleft()
if v==lst[count]:
count+=1
if i==m:
print(count)
else:
queue.append((i,v))complexity
Your code takes an input t representing the number of test cases. For each test case, it processes a list of integers, creates a deque, sorts a copy of the list in reverse order, and then iterates through the deque. The goal seems to be to find the position of an element specified by m after the list has been sorted. The time complexity of the code is O(n log n) due to the sorting operation, and the space complexity is O(n).
Let's break down the time and space complexities:
Time Complexity:
Input Reading (constant time per test case):
Reading t takes constant time.
Loop over Test Cases (O(t)):
The loop runs for each test case.
List Creation (O(n)):
Creating the list takes linear time in the size of the input.
Deque Creation (O(n)):
Creating the deque takes linear time in the size of the input.
Sorting (O(n log n)):
Sorting the list takes O(n log n) time.
Loop over Deque (O(n)):
The while loop processes each element in the deque once.
The overall time complexity is dominated by the sorting step, resulting in O(t * (n + n log n)).
Space Complexity:
Input Variables (constant space per test case):
Variables like n, m, lst, queue, count, i, and v use constant space per test case.
List (O(n)):
The list lst uses linear space in the size of the input.
Deque (O(n)):
The deque queue uses linear space in the size of the input.
Sorting (O(n)):
The sorting operation typically uses additional linear space.
The overall space complexity is dominated by the deque and the list, resulting in O(n) space.
In summary, the time complexity is O(t * (n + n log n)), and the space complexity is O(n).
