All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Vanya and Array
Tag(s):

Ad-Hoc, BIT, Data Structures, Easy-Medium, Sorting

Problem
Editorial
Analytics

Let's define $$2$$ functions a function $$F(i)$$ and $$Val(i,j)$$ for an Array $$A$$ of size $$N$$ as follows:

$$F(i) =$$ $$ \sum_{j=i+1}^{N} Val(i,j) $$

$$ Val(i,j) =$$ $$1$$ ,if $$A[i] < A[j]$$, else, $$Val(i,j) =$$ $$0$$.

Now, Vanya has been given one such array $$A$$ of size $$N$$ and an integer $$K$$. She needs to find the number of Distinct Unordered Pairs of elements $$(a,b)$$ in array $$A$$ such that $$F(a) +F(b) \ge K$$.

Input Format:

The first line contains $$2$$ space separated integers $$N$$ and $$K$$ denoting the size of array $$A$$ and the integer $$k$$ from the description given above. The next line contains $$N$$ space separated integers denoting the elements of array $$A$$ .

Output Format:

You need to print the required answer on a single line.

Constraints:

Subtask 1: (Worth 40% of the total points):

$$ 1 \le N \le 5000 $$

$$ 1 \le A[i] \le 10^5 $$

$$ 0 \le K \le 10^4 $$

Subtask 2: (Worth 60% of the total points) :

$$ 1 \le N \le 10^6 $$

$$ 1 \le A[i] \le 10^9 $$

$$ 0 \le K \le 10^9 $$

SAMPLE INPUT
8 10
1 3 2 4 5 6 8 7
SAMPLE OUTPUT
5
Explanation

Here the values of Function $$F(x)$$ for all the elements of Array $$A$$ from $$1$$ to $$N$$ are:

$$ [7,5,5,4,3,2,0,0]$$

So, the following 5 unordered pairs are considered:

$$ (1,2) $$

$$ (1,3) $$

$$ (1,4) $$

$$ (1, 5) $$

$$ (2,3) $$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Moonfrog Labs

Challenge Name

Moonfrog Labs Backend Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications