Apple trees 2 - MarisaOJ: Marisa Online Judge

Marisa planted

n

$n$ apple trees in a row. There are

q

$q$ rainy days. On each day

i

$i$ , a certain amount of rainwater, denoted as

w_{i}

$w_i$ liters, was received by each tree within the range

[l_{i}, r_{i}]

$[l_i, r_i]$ . Each tree, denoted as the

i^{t h}

$i^{th}$ tree, requires a specific amount of water, denoted as

A_{i}

$A_i$ liters, in order to undergo mutation. Marisa seeks to determine the day on which each tree mutates. ### Input - The first line contains two integers

n, q

$n,q$ . - The second line contains

n

$n$ integer

A_{i}

$A_i$ . - The next

q

$q$ lines, each line three integers

l_{i}, r_{i}, w_{i}

$l_i,r_i,w_i$ . ### Output - Print

n

$n$ integers, the

i^{t h}

$i^{th}$ one is the day on which tree

i

$i$ mutates. Or print

- 1

$-1$ if it won't mutate. ### Constraints -

1 \leq n, q \leq 10^{5}

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

1 \leq l_{i} \leq r_{i} \leq n

$1 \le l_i \le r_i \le n$ . -

1 \leq w_{i}, A_{i} \leq 10^{9}

$1 \le w_i,A_i \le 10^9$ . ### Example Input:

5337216153232353

$5 3 3 7 2 1 6 1 5 3 2 3 2 3 5 3$

Output:

1 - 1113

$1 -1 1 1 3$

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

Topic

Binary search

Rating

1700

Solution (1)

Solution