All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Class representatives

Advanced Data Structures, Data Structures, Longest Increasing Subsequence, Medium, Segment Trees


John teaches a class of \(n \) students. Each student is assigned a unique roll number from \(1\) to \(n\). He also knows the heights of each student. He needs to select a set of class representatives (a class can have any number of representatives).

A set of students are valid candidates for representatives if the following condition holds:

  • There does not exist a pair of students \(i,j\) such that \(roll[i]<roll[j]\) and \(height[i]\ge height[j]\).

John wants to select the maximum number of students as class representatives. However, he has a new student that got enrolled whose height is \(x\). In order to increase the number of class representatives, John assigns him a roll number \(i\) (from \(1\) to \(n+1\)) randomly and then increases the roll numbers of all those students by \(1\) whose roll number is \(\ge\) \(i\). If the number of class representatives does not increase after this process, then he repeats the same procedure (he again assigns him a roll number from \(1\) to \(n+1\)  randomly after reverting the roll numbers of all the existing students from \(1\) to \(n\)). Determine the expected number of times John needs to repeat this procedure in order to increase the number of class representatives.

Input format

  • First line: Two integers \(n\) (the number of students) and \(x\) (the height of the new student)
  • Next \(n\) lines: Two integers \(r_i\) and \(h_i\) denoting the roll number and height of the \(i^{th}\) student. It is guaranteed that no two students have the same roll number.

Output format

Print the expected number of times John needs to assign the roll number to the new student using the above procedure to increase the number of class representatives. If the expected value is of the form \(\frac{a}{b}\), then print \(a\cdot b^{-1}\) modulo \(10^{9}+7\) . If it is not possible to increase the number of class representatives, then print \(-1\)


\(1 \le n \le 500000\)

\(1 \le r_i \le n\)

\(1 \le x,hi \le 10^7\)

5 10
1 2
2 9
3 3
4 1
5 12

The number of class representatives can be increased from 3 to 4 by assigning the new student roll number 3,4 or 5.

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

November Easy' 18

View All Notifications