Блог пользователя prudent

Автор prudent, история, 6 лет назад, По-английски

Given 3 permutations of equal lengths n ≤ 105, let's call them A, B and C.
Find number of such i-s that there's no such j, that (Ai > Aj and Bi > Bj and Ci > Cj)

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Let's turn the input into triples Ti = (Ai, Bi, Ci).

Sort the triples into increasing order by Ci.

In addition, we'll make a set of pairs of integers, initially empty. We'll store pairs {Aj, Bj} here, keeping the invariant that there are no two pairs {Aj, Bj} and {Ai, Bi} in the set such that Aj < Ai and Bj < Bi.

Now loop from i = n - 1 to i = 0. At every i, Find from the set the smallest element that is larger than or equal to {Ai, Bi}. Let's say that element is {Aj, Bj}.

Since the pair is larger than equal to {Ai, Bi}, Aj > Ai. Then just check if Bj > Bi. If it is, this i won't be counted, since Tj is larger at all three parts.

Otherwise, we'll increment the result by one, and add {Ai, Bi} to the set. To maintain the invariant, while the largest pair that is smaller than {Ai, Bi} in the set is also smaller in its B-part, we'll remove it. We insert at most n elements into the set, and each element obviously gets removed at most once, so this part doesn't affect the overall complexity.

In the end just output the result. total time complexity is .