DMOPC '16 Contest 4 P6 - Molly and Flying Drones

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 64M

Authors:

WallE256, ionutpop118

Problem types

While wandering around the city, Molly got distracted by a drone shop and went in. In the shop, there were $Q$ ~Q~ drones available for purchase. Molly lives in a city where there are $N$ ~N~ buildings in a line, each with specific heights $h_i$ ~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$ ~x_k~ and $y_k$ ~y_k~.

Constraints

For all subtasks:

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

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

Subtask 1 [5%]

$N = 1$ ~N = 1~

$Q = 1$ ~Q = 1~

Subtask 2 [25%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$1 \le Q \le 15\,000$ ~1 \le Q \le 15\,000~

Subtask 3 [70%]

$1 \le N \le 1\,000\,000$ ~1 \le N \le 1\,000\,000~

$1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~

Input Specification

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

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

Output Specification

Your program should output $Q$ ~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

Comments

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$ ~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$ ~x_k~.

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

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