Apple trees 3 - MarisaOJ: Marisa Online Judge

Marisa planted

$n$ apple trees in a row, the

$i^{th}$ tree product apples of size

$A_i$ . There are

$q$ customers who wish to purchase apples. Each customer, denoted by the index

$i$ , has a specific requirement of purchasing

$a_i$ apples within a given size range,

$[l_i, r_i]$ . Additionally, each customer starts purchasing apples from tree

$x_i$ . Whenever a customer encounters an apple tree that offers apples within their desired size range, they will purchase one apple from that tree. Once a customer has bought the required number of apples, they will stop purchasing. Help Marisa determine for each customer, at which tree will he stop. ### Input - The first line contains two integers

$n,q$ . - The second line contains

$n$ integer

$A_i$ . - The next

$q$ lines, each line four integers

$l_i,r_i,x_i,a_i$ . ### Output - Print

$q$ integers, the

$i^{th}$ integer is the tree at which customer

$i$ will stop. In case the customer cannot buy enough apples, print

$-1$ . ### Constraints -

$1 \le n,q \le 10^5$ . -

$1 \le A_i \le 10^5$ . -

$1 \le l_i \le r_i \le 10^5$ . -

$1 \le x_i,a_i \le n$ . ### Example Input:

$9 10 10 6 6 10 6 6 7 9 3 10 14 9 1 9 12 3 1 5 18 5 2 13 17 9 2 2 7 3 2 6 14 2 2 5 12 4 2 3 11 3 1 7 11 5 1 15 19 5 2$

Output:

$-1 4 6 -1 5 3 5 3 7 -1$

Parallel binary search
	Apple trees
	Apple trees 2
	Apple trees 3
	Apple trees 4

Topic

Binary search

Data structure

Rating

1800

Solution (1)

Solution