DMOPC '14 Contest 2 P6 - Selective Cutting

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.25s
Java 1.0s
Python 1.0s
Memory limit: 128M

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

The Logging Company has been hit with a petition from concerned citizens regarding their uncontrolled tree-cutting. For public relations purposes, they have decided that, moving forward, they will only cut down trees with mass above a certain threshold.

The Logging Company has a line of N (1 \le N \le 100\,000) trees. Each tree i has a mass m_i (1 \le m_i \le 20\,000). The Company wants to cut some of the trees, so they've hired you to calculate the mass of all the wood they would get from cutting all the trees with m_i greater than or equal to q (1 \le q \le 20\,000) between positions a and b inclusive (0 \le a \le b < N). In particular, they want you to answer Q (1 \le Q \le 100\,000) such queries.

Input Specification

The first line will contain the integer N. For each tree i, the i^{th} (from 0) integer on the second line will contain the integer mass m_i. The third line will contain the number Q, the number of queries the logging company wants you to answer. The next Q lines will contain three integers a and b and q.

Output Specification

For each query, print the total mass of the trees at position i such that a \le i \le b, and m_i \ge q.

Sample Input

1 3 4 2 5
0 4 3
1 3 2
0 4 5
4 4 1
0 4 1

Sample Output



  • 5
    Chris_Xie  commented on April 11, 2018, 10:02 a.m. edit 2

    Typo in Input Specification

    The first line will contain the integer N. For each tree i, the ith (from 0) integer on th second line

    Should be "the second line".

  • -6
    Xue_Alex  commented on July 19, 2017, 5:26 p.m.

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

  • 1
    pyrexshorts  commented on March 28, 2015, 12:14 a.m.

    My solution doesn't work for the 3rd batch test case, can anyone give me a hint why?

    • 7
      bruce  commented on March 28, 2015, 12:03 p.m.

      2 mistakes in your code: 1) "ans" in your query structure is int, not long long. It will overflow. 2) x=max(x,q) is not right, since some mass is much larger than the query. Your solution ignores all masses which are bigger than the largest query. So, x in your code should be the largest of all a and all q. Fix these mistakes, you'll AC.

  • 0
    pop  commented on March 26, 2015, 11:07 p.m.

    Can anyone share an algorithm that doesn't involve iterating through all trees from a - b?

    • 3
      kobortor  commented on March 26, 2015, 11:12 p.m. edited

      I would, but if I did fatal would get mad at me for violating TOS and stuff.

      Edit: Xyene is nice.

      • 0
        pop  commented on March 26, 2015, 11:16 p.m.

        Ah. sorry. I wasn't aware. I'm more interested in the learning aspect than the points system. I've see what you mean in the TOS.

    • 2
      Xyene  commented on March 26, 2015, 11:11 p.m.

      There are multiple ways to approach this problem. One is the Binary Indexed Tree.

      • 1
        pop  commented on March 26, 2015, 11:17 p.m. edited

        Thank you

  • 2
    pyrexshorts  commented on March 26, 2015, 10:44 p.m. edited

    Can someone tell me why I have RTE in the first test case? Thanks!

    Edit: Figured it out, never mind.

  • 1
    bobhob314  commented on Jan. 4, 2015, 6:54 p.m.

    "For each tree i, line i+2 will contain the integer mass mi" All of the masses are on one line in the sample input.