RGPC '17 P2 - Cubes are Life - Olympiads Online Judge

RGPC '17 P2 - Cubes are Life

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

Because Gabriel got an early offer from UOIT, his overjoyed parents gave him a lot of Rubik's Cubes as a reward. However, he soon developed Carpal Tunnel Syndrome, and now has to sell some of his cubes at half of their original price to pay for his medical bills.

Gabriel is a very unique person; the $N$ $N$ cubes that he got each have a distinct value $V_i$ $V_{i}$ , and are placed in a straight line. He wants to know if he has a total of at least $M$ $M$ dollars after he sells all of his cubes inclusively between the one valued at $V_a$ $V_{a}$ and the one valued at $V_b$ $V_{b}$ (in the line). He specifically wants to ask $Q$ $Q$ questions in the form $(V_a, V_b)$ $(V_{a}, V_{b})$ to know if he has enough money after selling all of the cubes in that range. Both cubes are guaranteed to exist in the sequence.

Note: it may be helpful to use unsigned 64-bit variables (e.g. unsigned long long in C++).

Constraints

Subtask 1 [10%]

$1 \le N, Q \le 100$ $1 \leq N, Q \leq 100$
$1 \le M, V \le 1\,000$ $1 \leq M, V \leq 1 000$

Subtask 2 [90%]

$1 \le N, Q \le 100\,000$ $1 \leq N, Q \leq 100 000$
$1 \le M \le 10\,000\,000$ $1 \leq M \leq 10 000 000$
$1 \le V \le 1\,000\,000$ $1 \leq V \leq 1 000 000$

Input Specification

The first line of input will consist of 3 space-separated integers $N$ $N$ , $M$ $M$ , and $Q$ $Q$ . The next line will contain $N$ $N$ space-separated integers, where the $i^{th}$ $i^{t h}$ integer represents the ${V_i}^{th}$ ${V_{i}}^{t h}$ value. For the next $Q$ $Q$ lines, each line will contain 2 space separated integers $V_a$ $V_{a}$ and $V_b$ $V_{b}$ .

Output Specification

For each question, output Enough if Gabriel can afford his bills or Not enough if he cannot.

Sample Input

Copy

Sample Output

Copy

Not enough
Enough

Comments

2

moladan123 commented on Feb. 18, 2017, 3:42 a.m.

This problem is extremely similar to DMOPC '14 Contest 2 P4 - Deforestation. Just for the record.

3

Dankat commented on Feb. 18, 2017, 3:56 a.m.

It's a coincidence and there is a slight difference.

-1

jimgao commented on Feb. 13, 2017, 7:14 p.m.

Are the prices multiples of 2?

0

chenj commented on Feb. 13, 2017, 9:50 p.m.

Not necessarily. If the total price after halving isn't exactly $M$ $M$ or greater, then it's Not enough.