Allen's Segments

View as PDF

Submit solution

Points: 17
Time limit: 0.6s
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

Credit to AQT for tweaking the problem to be harder.

Dormi is having trouble with his Latin homework. Since he wants to study for his summatives, he has translated the problem and entrusted you with this task instead.

He has given you N segments. Segment i covers the interval (L_i, R_i) and has a value V_i. We say that segment i covers segment j if every point in j is inside segment i, and this would still hold true if segment j were shifted to the left or to the right by 0.5. These N segments are special - if two segments share a point, then the larger segment covers the smaller segment.

He gives you Q queries in the form of a b. For each query, find the ID of the segment with lowest value that covers both segments a and b. If there are no such segments, output -1.

If there is more than one segment that covers a and b of the same value, output the one of smallest length.

Please help Dormi solve this problem!

Input Specification

A single integer N (1 \le N \le 10^5), followed by N lines in the form L_i\ R_i\ V_i (1 \le L_i < R_i \le 10^9) (1 \le V_i \le 10^9).

The next line will contain a single integer Q (1 \le Q \le 10^5), followed by Q queries in the form a b.

Output Specification

Q lines, the answer to the i^{th} query.

Sample Input 1

2 3 2
1 6 10
4 5 3
1 3
1 2

Sample Output 1



  • 1
    Plasmatic  commented on Feb. 10, 2020, 11:45 p.m.

    Are the segments distinct?

    • 3
      zxyl  commented on Feb. 11, 2020, 9:50 a.m.

      In other words, there cannot be any two segments that partially share a range (this includes the ends).