I have a question for you: how long do you usually try to solve a problem before looking at the solution? I’d really appreciate it if you could share your experience with me.

I was solving a problem where we have k intervals, and we need to count the number of nested pairs.

More formally, count pairs (i, j) such that:

l_i < l_j <= r_j < r_i

(or equivalently after sorting by the left endpoint, count previous intervals whose right endpoint is greater than or equal to the current one).

The standard solution is:

1. Sort intervals by the left endpoint.
2. Insert right endpoints into an ordered_set (PBDS).
3. Use order_of_key() to count how many previous right endpoints are greater than or equal to the current one.

This gives an O(n log n) solution.

My question is:

Is there an O(n log n) or O(n) solution that does not use PBDS (ordered_set), GNU extensions, or similar policy-based data structures?

I'm looking for alternatives using only standard C++ (STL). Thanks!

Hi everyone, I've come across an interesting algorithmic problem and wanted to hear your thoughts on how to solve it efficiently. Problem Statement: Suppose we have an array of elements, and we are given a frequency array cnt, where cnt[i] represents how many times the $$$i$$$-th element appears.In each operation, we are allowed to choose two distinct elements (i.e., elements with different values) and remove both of them from the array. We want to find the minimum possible number of elements remaining in the array after performing this operation as many times as possible.What is the most efficient algorithm or mathematical approach to solve this? Can we find the answer without actually simulating the removals? Thanks in advance for your ideas!

In some Codeforces problems (for example, problem 545C), you may notice two different interval notations, such as:

[a, b] and [a; b]

This can be confusing at first, but there is actually no difference in meaning.

In many Russian mathematical texts, the semicolon ; is used as the separator in intervals, while in most European and English texts, the comma , is used instead. Since many Codeforces problems are translated from Russian, both notations can appear.