DMOPC '16 Contest 4 P6 - Molly and Flying Drones

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

While wandering around the city, Molly got distracted by a drone shop and went in. In the shop, there were Q drones available for purchase. Molly lives in a city where there are N buildings in a line, each with specific heights h_i. Being cheap, the drones from this shop have some weird technical specifications, the height interval that they need to start from. With this in mind, Molly asks you to tell her how many contiguous subsequences of buildings have the shortest building in the specified range of each drone, x_k and y_k.


For all subtasks:

1 \le h_i \le 1\,000\,000 where 1 \le i \le N.

1 \le x_k \le y_k \le 1\,000\,000 where 1 \le k \le Q.

Subtask 1 [5%]

N = 1

Q = 1

Subtask 2 [25%]

1 \le N \le 1\,000

1 \le Q \le 15\,000

Subtask 3 [70%]

1 \le N \le 1\,000\,000

1 \le Q \le 100\,000

Input Specification

The first line of input will contain two space-separated integers, N and Q.
The second line of input will contain N space-separated integers, h_i where 1 \le i \le N.
The next Q lines of input will each contain two space-separated integers, x_k and y_k.

Note: Fast I/O methods are recommended for this problem.

Output Specification

Your program should output Q integers on different lines, representing the number requested for each drone.

Sample Input

5 1
3 2 4 5 3
3 4

Sample Output



  • 3
    Cueball1234  commented on April 4, 2018, 7:27 p.m.

    RTE bad_alloc

    I am using Segment Tree to solve this problem. However, it is giving me RTE (std::bad_alloc), despite the fact that I only used 54.9 MB. I was wondering why this is happening, and how I may fix this issue? Thank you!

    • -3
      Plasmatic  commented on July 28, 2018, 7:13 p.m.

      maybe try pre allocating the thing

  • 3
    pulkitsja  commented on Feb. 16, 2017, 4:29 a.m.

    Will there be some short editorials or write-ups?

    • 23
      percywtc  commented on Feb. 16, 2017, 1:57 p.m. edited

      Hi. Although I am just a contestant and I don't know about the editorials, I would like to share my solution, which I hope it helps.

      It is obvious that no ranges can include elements less than x_k, and thus, my first idea is to breaking the cities into several parts, only parts of contiguous ranges that no elements are less than x_k.

      By considering arrays with no elements less than x_k. It is easy to observe that the number of valid subarrays is the number of subarrays can be built, minus the number of subarrays with all elements greater than y_k.

      Using the above observations, we can precompute the number of subarrays with all elements greater than i for each 1 \le i \le \max(h_i). Let's denote this result as f(i). And thus, the answer for each query is f(x_k)-f(y_k+1).

      • 2
        pulkitsja  commented on Feb. 16, 2017, 7:36 p.m.

        Thank You.

  • 0
    zscoder  commented on Feb. 15, 2017, 12:34 p.m.

    If I submit multiple solutions will all of them be counted during system tests or just the last one?

    • 0
      k_53P  commented on Feb. 15, 2017, 1:14 p.m. edited

      All submissions made during your contest window will be judged on system tests. Your score will be based on the highest scoring submission.

      Edit: However, resubmitting can increase the time for the problem, which is considered when tie-breaking contestants with the same number of points.

      • 0
        zscoder  commented on Feb. 15, 2017, 1:22 p.m.

        If I submit at 1:00:00 and submit again at 1:30:00, and actually both passes system test, which submission is considered?

        • 0
          k_53P  commented on Feb. 15, 2017, 1:29 p.m.

          If multiple submissions have the same score, the system currently considers the one with the latest time, so the 1:30:00 submission will be used.