JAPC1005 Editorial

Practice

Contest

Author: A Rupeswar Subudhi

Tester: Pritish Priyatosh Nayak

Editorialist: A Rupeswar Subudhi

Easy-Medium

PREREQUISITES:

set, data structures

PROBLEM:

Given the number of problems solved n and total penalty time p of N teams, determine for Q queries, the number of teams which share the rth place.

EXPLANATION:

All we need to do is simply sort the teams in descending order of their number of problems solved n and then sort the teams with equal n in ascending order of their total penalty time p in an array A.

Now, we have to find a way to determine the number of teams that share the rth rank.

One way is to maintain an ordered map where the keys are the intervals of the indexes of A such that all the teams which have their indices in the same interval have equal n and p and their respective values will be the size of the interval.

Now, for each query, we have a rank r whose answer is to be determined.

We know that the team at rth index of A must share the rank r.

Hence, we will now make an interval of size 1 starting from r and ending at r and search for the interval in our map that overlaps with our query interval. Since the size of our query interval is 1, the query interval will completely lie within some interval in our map and that interval contains all the teams that share the same rank and in our case, the rth rank.

Once we get our interval, we will just print itâ€™s corresponding value in the map since that is the size of the interval and hence the number of teams that share the rank r.

Time Complexity : O(T * N * log(N))