RoAlgo Contest #11 - Back to School 2024 | Remove Inversions

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s Memory limit: 256MB Input: Output:

Task

You are given an array AA of NN elements. We define an inversion as a pair of indices (i,j)(i, j) where 1i<jN1 \leq i < j \leq N and Ai>AjA_i > A_j.

An operation is defined as the removal of an element.

You need to print the number of ways to perform a maximum of 2 operations such that the remaining array has exactly KK inversions.

Input data

The first line of input contains two numbers, NN and KK. These represent the number of elements in the array and the desired number of inversions after performing the operations, respectively. The second line contains NN elements representing the array AA.

Output data

Print the total number of ways to remove elements.

Constraints and clarifications

  • 1N21051 \leq N \leq 2 \cdot 10^5
  • 0KN(N1)20 \leq K \leq \frac{N \cdot (N - 1)}{2}
  • 1Ai21051 \leq A_i \leq 2 \cdot 10^5, for 1iN1 \leq i \leq N

Subtasks

  • For 15 points, 1N2001 \leq N \leq 200.
  • For another 20 points, 201N104201 \leq N \leq 10^4.
  • For another 20 points, 104N210510^4 \leq N \leq 2 \cdot 10^5 şi 1Ai261 \leq A_i \leq 26.
  • For another 45 points, 104+1N210510^4+1 \leq N \leq 2 \cdot 10^5.

Example 1

stdin

6 2
1 5 2 3 4 1

stdout

6

Explanation

The 66 ways to remove two elements are: [2,3][2,3], [2,4][2,4], [2,5][2,5], [3,6][3,6], [4,6][4,6], [5,6][5,6].

Example 2

stdin

8 16
1 5 4 5 2 1 1 1

stdout

2

Explanation

The two ways are either not to remove any element or to remove the first element.

Log in or sign up to be able to send submissions!