Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hablu's Team

By shihan04 · Limits 1s, 512 MB

This year Hablu wants to participate in ICPC. He studies in “Habagoba University” along with nn other students. Everyone in the University has a “Problem solving skill level”. Hablu needs 2 other members to make a team.

But Hablu is really dumb! He will select two students if and only if the summation of their “Problem solving skill level”s is less than his own (What?)!

Now your task is to calculate how many ways Hablu can make his team. Two teams are considered different if a student xx is on the first team but not on the second one.


In the first line you will be given two integers nn and kk (1n,k1051 \leq n, k \leq 10^5) representing the number of students other than Hablu and Hablu's “Problem solving skill level” respectively. Next line will contain nn integers aia_i (1ai1051 \leq a_i \leq 10^5) — the “Problem solving skill level”s of other students.


Output a single integer — the number of ways Hablu can make his team.


4 10
1 1 2 7
5 1
1 2 3 4 5

Output may not fit into 32 bit integer. Use 64 bit integer.



67% Solution Ratio

nuipqiunEarliest, Apr '20

md_jakariyaFastest, 0.0s

Lazy_ProgrammerLightest, 131 kB

mdvirusShortest, 169B


Login to submit


You can just do binary search and solve it in O(nlogn)O(nlogn)O(nlogn) time complexity. #include<...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.