GCC '16 P3 - Hang Gliding Fun

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Java 8 1.4s
Memory limit: 256M

Problem types
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

Bob lives in a city with N skyscrapers arranged in a row running north to south. He likes to hang glide over the city. Bob can glide south to a shorter building if all of the passed buildings' heights are smaller than his current building's height.

Each of the N buildings has height h_i, view value v_i, and danger value d_i for 1\le i\le N. Bob has Q questions for you: Given that he starts at the B^{th} northmost building (1\le B\le N), what is the maximum possible sum of the view values of buildings which he lands on such that none of those buildings has danger value more than M (1\le M \le 10^6)?

Input Specification

The first line contains two space-separated numbers N (1 \le N \le 100\,000) and Q (1 \le Q \le 100\,000), the number of buildings and queries respectively.
The next N lines each contain h_i (1\le h_i\le 10^6), v_i (1\le v_i\le 10^6), and d_i (1\le d_i\le 10^6), the height, view value, and danger value for the i^{th} northmost building.
The next Q lines each contain the query. Each line contains two space-separated numbers B (1\le B\le N) and M (1\le M\le 10^6). It is guaranteed that the danger value of the B^{th} northmost building is not more than M.

Output Specification

For each query, output the answer on a new line.

Sample Input 1

3 2
3 1 2
3 4 4
1 2 10
2 20
2 4

Sample Output 1



For the first query, the path which maximizes the sum of view values is hang gliding to the third building, so the answer is 4+2. For the second query, the path which maximizes the sum of view values is simply staying put at the second building, so the answer is 4.


  • -16
    r3mark  commented on May 12, 2017, 3:10 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.