All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Class representatives
Tag(s):

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

Problem
Editorial
Analytics

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\)

Constraints

\(1 \le n \le 500000\)

\(1 \le r_i \le n\)

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

SAMPLE INPUT
5 10
1 2
2 9
3 3
4 1
5 12
SAMPLE OUTPUT
2
Explanation

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), 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?