Balkan OI '11 P6 - Trapezoids

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Consider two arbitrarily chosen horizontal lines. A trapezoid T_i between these lines has two vertices situated on the upper line and the other two vertices on the lower line (see figure below). We will denote by a_i, b_i, c_i and d_i the upper left, upper right, lower left and respectively lower right vertices of the trapezoid T_i. A subset S of trapezoids is called independent if no two trapezoids from S intersect.


Determine the cardinality of the largest independent set of trapezoids (the largest set means the set with most elements). Also find the count of different independent sets with maximum cardinality. Find this count modulo 30\,013.

Input Specification

The first line of input contains one integer N – the number of trapezoids. Each of the next N lines contains four integers a_i, b_i, c_i and d_i. No two trapezoids have a common vertex (corner).

Output Specification

The only line of output should contain two numbers separated by space: firstly, the cardinality of the largest independent set; secondly, the count of different independent sets with maximum cardinality modulo 30\,013.


  • 1 \le N \le 100\,000
  • 1 \le a_i, b_i, c_i, d_i \le 1\,000\,000\,000
  • If only the first number in the output is correct you will get 40\% of the test score.
  • 40\% of the tests will have N \le 5\,000

Sample Input

1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31

Sample Output

3 8

Explantion for Sample Output

The picture below is not an accurate representation. The trapezoids' top and bottom have been shifted up and down for visibility.


There are no comments at the moment.