# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Toph will be unavailable for 30 minutes starting from 16:30 UTC +6 (June 2, 2019) due to planned maintenance. We are sorry for any inconvenience this may cause.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A frog wants to cross a river. There are some posts in the river. The frog can go from one post to another by jumping. All the posts are located in a single line and numbered from **1** to **N** and distance between **i-th** post and **(i+1)-th** post is **1**. Distance between the **1**^{st} post and the starting position is **1** and distance between the **N**^{th} post and the other side of the river **1**. The frog can jump at most **X**_{i} distance from **i**^{th} post. Now you have to answer if there is any path that the frog can take to cross the river.

Input starts with an integer **T (≤ 5)**, denoting the number of test cases.

Each case starts with two integers **N **and** Q **where **N** is the number of posts and **Q** is number of queries**. **Next line contains **N **integers separated by spaces and the** i’th** integer of this line represents the strength **X**_{i }of the **i’th** post. Next **Q **lines will contain two or three integers each**. **First number **t** represents the type of query.

- If
**t = 1**, there will be 2 more integers**p**,**s**meaning that**p**^{th}post’s strength changes to**s**. - If
**t = 2**, there will be one more integer**s**meaning that frogs can jump at most**s**distance from starting point.

**Constraints:**

**(1 ≤ N ≤ 100,000)****(1 ≤ Q ≤ 100,000)****(0 ≤****X****i****≤ 1000,000,000)****(1 ≤ t ≤ 2)****(1 ≤ p ≤ N)****(0 ≤ s ≤ 1000,000,000)**

For each case, print the case number in one line and for each query type of 2 output **“yes”** if the frog can go to other side with current configuration or **“no”** otherwise in one line.

Input | Output |
---|---|

1 5 11 0 0 1 5 3 2 1 2 2 2 3 2 4 2 5 1 4 0 2 1 2 5 2 3 1 1 4 2 1 | Case 1: no no yes yes yes no yes no yes |

73% Solution Ratio

aaman007Earliest,

RobbinFastest, 0.1s

ShadowMeLightest, 2.0 MB

muradhossenShortest, 1726B

Login to submit