## DMOPC '16 Contest 4 P6 - Molly and Flying Drones

View as PDF

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

Authors:
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

While wandering around the city, Molly got distracted by a drone shop, and went in. In the shop there where drones available for purchase. Molly lives in a city where there are building in a line, each with specific heights . 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, and .

• where
• where

#### Input Specification

The first line of input will contain two space-separated integers, and .
The second line of input will contain space-separated integers, where .
The next lines of input will each contain two space-separated integers, and .

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

#### Output Specification

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

#### Sample Input

5 1
3 2 4 5 3
3 4

#### Sample Output

6

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

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!

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

maybe try pre allocating the thing

• commented on Feb. 17, 2017, 2:39 p.m. edited

nvm

• commented on Feb. 15, 2017, 11:29 p.m.

Will there be some short editorials or write-ups?

• commented on Feb. 16, 2017, 8:57 a.m.

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 , and thus, my first idea is to breaking the cities into several parts, only parts of contiguous ranges that no elements are less than .

By considering arrays with no elements less than . 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 .

Using the above observations, we can precompute the number of subarrays with all elements greater than for each . Let's denote this result as . And thus, the answer for each query is .

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

Thank You.

• commented on Feb. 15, 2017, 7:34 a.m.

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

• commented on Feb. 15, 2017, 8:14 a.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.

• commented on Feb. 15, 2017, 8:22 a.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?

• commented on Feb. 15, 2017, 8:29 a.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.

• commented on Feb. 15, 2017, 6:56 a.m. edited

is the entire sequence not a subsequence?