COCI '23 Contest 2 #5 Zatopljenje

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

It's winter, it has never been colder, and Mr. Malnar is looking at his photos from his last cruise on the Adriatic and recalls unforgettable moments. The TV is on in the background, broadcasting news about the latest proposals for measures to slow down sea level rise. Looking at his photos of the coast, Mr. Malnar asks himself what the photos would have looked like if the sea level had risen a certain amount. There are so many pictures, and even more questions, so Mr. Malnar asks for your help.

We imagine the coast as a sequence of $n$ ~n~ numbers $h_1, h_2, \ldots, h_n$ ~h_1, h_2, \ldots, h_n~, where the $i$ ~i~-th number represents the terrain height at the $i$ ~i~-th point. Mr. Malnar has $q$ ~q~ queries, where the $i$ ~i~-th query is as following: How many islands would there be between the $l_i$ ~l_i~-th and $r_i$ ~r_i~-th point if the sea level rose by $x_i$ ~x_i~ meters?

The left image shows the first query of the first sample test case, and the right image shows the second query of the second sample test case.
The left islands correspond to intervals $[2, 2]$ ~[2, 2]~ and $[4, 5]$ ~[4, 5]~.
The right islands correspond to intervals $[1, 1]$ ~[1, 1]~, $[4, 4]$ ~[4, 4]~, $[8, 8]$ ~[8, 8]~ and $[10, 10]$ ~[10, 10]~.

An island is defined as the maximal interval where every $h_i$ ~h_i~ is strictly greater than the sea level. A maximal interval is one that cannot be extended in either direction while keeping the mentioned condition true. Initially, the sea level is at $0$ ~0~ meters.

Input Specification

The first line contains integers $n$ ~n~ and $q$ ~q~ $(1 \le n, q \le 2 \cdot 10^5)$ ~(1 \le n, q \le 2 \cdot 10^5)~, the length of the sequence and the number of queries.

The second line contains $n$ ~n~ integers $h_1, h_2, \ldots, h_n$ ~h_1, h_2, \ldots, h_n~ $(0 \le h_i \le 10^9)$ ~(0 \le h_i \le 10^9)~ that describe the terrain of the coast.

In each of the next $q$ ~q~ lines there are three integers $l_i$ ~l_i~, $r_i$ ~r_i~ and $x_i$ ~x_i~ $(1 \le l_i \le r_i \le n, 0 \le x_i \le 10^9)$ that describe the $i$ ~i~-th query.

Output Specification

In the $i$ ~i~-th of the $q$ ~q~ lines, print the answer to the $i$ ~i~-th query. Each of the queries is independent of the others.

Constraints

Subtask	Points	Constraints
1	10	$n, q \le 2 \cdot 10^3$ ~n, q \le 2 \cdot 10^3~
2	20	$l_i = 1, r_i = n$ ~l_i = 1, r_i = n~ for all $i = 1, 2, \ldots, q$ ~i = 1, 2, \ldots, q~
3	20	There exists an integer $p$ ~p~ $(1 \le p \le n)$ ~(1 \le p \le n)~ such that the following holds: $h_1 \ge h_2 \ge \cdots \ge h_p$ ~h_1 \ge h_2 \ge \cdots \ge h_p~ and $h_p \le h_{p+1} \le \cdots \le h_n$ ~h_p \le h_{p+1} \le \cdots \le h_n~
4	60	No additional constraints.

Sample Input 1

6 3
2 4 2 3 4 1
2 5 2
3 5 3
3 4 4

Sample Output 1

2
1
0

Explanation for Sample 1

The first query is shown in the left image in the task description, the islands correspond to the intervals $[2, 2]$ ~[2, 2]~ and $[4, 5]$ ~[4, 5]~. In the second query, the island corresponds to the interval $[5, 5]$ ~[5, 5]~. In the third query, there are no islands because everything is under water.

Sample Input 2

10 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 2

Sample Output 2

2
4
3

Explanation for Sample 2

In the first query, the islands correspond to the intervals $[3, 5]$ ~[3, 5]~ and $[8, 9]$ ~[8, 9]~. In the second query (shown in the right image in the task description), the islands correspond to the intervals $[1, 1]$ ~[1, 1]~, $[4, 4]$ ~[4, 4]~, $[8, 8]$ ~[8, 8]~ and $[10, 10]$ ~[10, 10]~, while in the third query, the islands correspond to the intervals $[1, 1]$ ~[1, 1]~, $[3, 4]$ ~[3, 4]~ and $[8, 10]$ ~[8, 10]~.

Comments

There are no comments at the moment.