For the Lunar New Year festival this year, James was put in charge of coordinating the dragon dancers. He organized his team of $$$n$$$ dancers in a line such that position 1 is the front of the line. While he trained them all well, he forgot to consider one factor: their heights. When controlling the dragon puppet, it looks quite unnatural if two consecutive people in the line have their heights differ by too much. Additionally, they have been training in their current line order for so long that no dancer can dance directly behind a new person; they must either dance behind the same person or be the front of the line. James wants to pick some dancers from this line to perform in the dance tonight. Help him figure out the length of the longest possible line he can form for tonight's dragon dance!
The first line of input contains two integers $$$n$$$ ($$$1\leq n \leq 2\cdot10^5$$$) and $$$k$$$ ($$$1\leq k \leq 10^9$$$) — the number of dancers and the maximum absolute height difference allowed.
The second line contains $$$n$$$ integers $$$h_1,h_2,\dots,h_n$$$ ($$$1\leq h_i\leq 10^9$$$) — the heights of each of the dancers in the line in order.
The output should consist of a single integer indicating the length of the longest possible line James can form to ensure the dragon dance looks natural.
7 41 2 1 2 6 7 1
6
6 37 4 7 4 8 9
4
In the first sample, James picks the first 6 dancers since the gap between 7 and 1 is too large to be included in the line.
It's Lunar New Year, and $$$n$$$ ($$$1 \leq n \leq 100$$$) lion dancers are performing a traditional lion dance through a grid-like corridor. The corridor is divided into $$$m$$$ ($$$1 \leq m \leq 10^5$$$) sections, arranged as columns of platforms. Each section $$$i$$$ consists of $$$k_i$$$ platforms ($$$n \leq k_i \leq 10^5$$$) stacked vertically in a grid-like structure. Each platform can hold exactly one dancer, and no two dancers can share the same platform at any time.
The dancers start their performance in the first column and must move through the grid from left to right. At each step, all $$$n$$$ dancers move as a team to the next column, each landing on one of the available platforms in the new section. This process continues until they reach the final column.
Additionally, the lion dancers are numbered from $$$1$$$ to $$$n$$$, with dancer $$$1$$$ always performing on the lowest platform and dancer $$$n$$$ on the highest platform in any column. This order must be maintained throughout the performance: if dancer A is below dancer B in one column, then dancer A must be below dancer B in every other column.
Your task is to determine the number of distinct ways the lion dancers can perform their routine, moving from the first column to the last. Two routines are considered distinct if, at any step, at least one dancer occupies a different platform compared to the other routine. Please output the answer mod $$$10^9+7$$$.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — the number of lion dancers and corridor sections respectively.
The second line contains $$$m$$$ integers, $$$k_1, k_2, … k_{m}$$$ ($$$n \leq k_i \leq 10^5$$$) — denoting the number of platforms in each column.
Output a single integer — the number of distinct ways the lion dancers can complete their performance mod $$$10^9+7$$$
2 32 3 2
3
1 53 2 1 4 2
48
10 819 12 10 11 16 19 12 13
823844000
Horse is sitting on the Earth staring in the sky at the moon. However, he doesn't have great vision, so he needs your help to figure out the lunar phase! He is quite perceptive though and knows the location of the moon as well as where the sun's rays are coming from. More specifically, the Earth is located at the origin $$$(0, 0)$$$, and the sun's rays are parallel to the vector $$$(s_x, s_y)$$$. Furthermore, the moon is located at $$$(m_x, m_y)$$$. The sun illuminates half of the moon, and a (potentially different) half of the moon is visible from the Earth. There are four events that Horse really cares about: the new moon, first quarter, full moon, and third quarter. Horse wants to know what is the next event that will occur. Horse has a lot of questions, so please answer them all.
Note that the moon moves counterclockwise around the origin. For more info on the moon phases, please check Wikipedia.
The first line contains a single number $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.
The following $$$q$$$ lines contain 4 integers $$$s_x, s_y, m_x, m_y$$$ ($$$-10^5 \leq s_x, s_y, m_x, m_y \leq 10^5$$$) — where $$$(s_x, s_y)$$$ is the vector the sun's rays are parallel to, and $$$(m_x, m_y)$$$ is the point the moon is located at.
It is guaranteed that $$$(m_x, m_y)$$$ is not the origin and that $$$(s_x, s_y) \neq (0, 0)$$$. Furthermore, the moon's state is more than $$$\frac{1}{360}$$$th of the lunar cycle away from an event.
41 1 1 01 1 0 -11 1 -1 01 1 0 1
Full moon First quarter New moon Third quarter
Xinyu the dragon is excited to attend the Lunar New Year festival to welcome in the new year!
At the festival there are $$$n$$$ lanterns lined up in a row, with the $$$i$$$th lantern being at height $$$a_i$$$. Xinyu the dragon loves hopping around on the lanterns, but he can only hop to adjacent lanterns that are the same height as the lantern he is currently on.
Fortunately, his powers of firebreathing give him the ability to do the following any number of times as he hops about:
Xinyu's goal is to pick some lantern to start on and then hop around to visit all of the lanterns. He is curious about how much energy he needs to do so, so he will ask you questions over time of the form $$$1\ p$$$, meaning he wants to know if he starts at lantern $$$p$$$, what is the minimum energy he needs to start with to be able to visit all the lanterns.
Additionally, as the festival progresses, the heights of individual lanterns may fluctuate, and these events will be presented in the form $$$2\ p\ x$$$, meaning that lantern $$$p$$$ now has a new height of $$$x$$$.
Please process each event and help answer Xinyu's questions as the festival progresses!
The first line of input contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n, q\leq 2\cdot10^5)$$$ — the number of lanterns and the number of events.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (0\leq a_i\leq 10^9)$$$ — the starting heights of each lantern in the row.
Each of the following $$$q$$$ lines will describe an event in one of the following formats:
There is guaranteed to be at least one event of the first type.
For each question that Xinyu asks, please print the answer on its own line.
3 23 1 31 11 2
0 2
2 51000000000 01 22 2 101 22 1 101 2
1000000000 999999990 0
In the first test case, if Xinyu starts on lantern 1 with 0 energy, he can absorb fire 2 times to decrease the lantern's height by 2 and increase his energy by 2, then hop to lantern 2, spend 2 energy to raise its height from 1 to 3, then hop to lantern 3.
If he starts on lantern 2 with 2 energy, he can spend 2 energy to raise its height from 1 to 3, then hop freely to lanterns 1 and 3.
Chen lives in a 2D world. To celebrate the end of the Year of the Dragon, $$$n$$$ dragons are flying around in the sky.
We can think of this world as an $$$m$$$ wide grid, labeled horizontally from $$$1$$$ to $$$m$$$ and vertically from $$$0$$$ to $$$\infty$$$. Chen can only move horizontally along the line $$$y=0$$$. All dragons can be treated as perfectly horizontal height 1 rectangles, and they all fly above Chen.
The $$$i$$$th dragon spans horizontally from location $$$l_i$$$ to $$$r_i$$$, inclusive. Furthermore, each dragon is associated with an power value $$$p_i$$$. Let the locations that each dragon takes up be 1-indexed from left to right. Dragons get scalier as they grow, so $$$j$$$th index of the $$$i$$$th dragon has $$$p_i \cdot j$$$ scales on it.
For each position $$$i$$$, or coordinate $$$(i,0)$$$, that Chen can stand on, she wants to know how many scales would directly be above her.
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) - the number of dragon's and the total width of the grid.
Each of the following $$$n$$$ lines will contain 3 integers $$$l_i, r_i, p_i$$$ ($$$1 \leq l_i \leq r_i \leq m, 1 \leq p_i \leq 2 \cdot 10^6$$$) — denoting that the $$$i$$$th dragon stretches from index $$$l_i$$$ to $$$r_i$$$ and has power $$$p_i$$$.
Output $$$m$$$ space-separated integers, with the $$$i$$$th integer representing the number of scales above Chen if she is standing at position $$$i$$$.
2 41 3 14 4 5
1 2 3 5
2 61 6 13 4 4
1 2 7 12 5 6
In the first test case, the first dragon contributes 1 scale to position 1, 2 scales to position 2, 3 scales to position 3, and 0 scales to position 4. The second dragon contributes 5 scales to position 4
This is the easy version of the problem. The difference between the versions is that in this version $$$q = 0$$$.
Sally the Snake has found herself in a field of grass and rocks. The field can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Every cell in the grid is either '*' (grass) or '@' (rock).
Sally is a fast snake. Interestingly, she moves at a speed $$$k_v$$$ when moving up or down, while she moves at a speed of $$$k_h$$$ when moving left or right.
Sally is a peculiar snake, and every movement she takes must consist of the following steps:
Sally is a curious snake. She wants to know how many pairs of grass cells $$$a$$$ and $$$b$$$ there are such that $$$a \neq b$$$ and she can reach cell $$$b$$$ after some number of complete movements from cell $$$a$$$. She calls this quantity the openness of the field.
Sally is a stupid snake. She needs you to find this value for her!
Lastly, Sally is in danger for the next $$$q$$$ minutes. Each minute from $$$1$$$ to $$$q$$$, a rock will fall from the sky and land in some cell of the grid (that contained grass). The cell that the rock falls on will no longer have grass and should be considered a rock cell.
Please help Sally by finding the openness of the field before any rocks fall, as well as after each rock falls onto the grid.
The first line of input will contain four integers $$$n$$$, $$$m$$$, $$$k_v$$$, and $$$k_h$$$ ($$$2 \leq n, m \leq 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$, $$$1 \leq k_v \lt n$$$, $$$1 \leq k_h \lt m$$$) — denoting the number of rows in the grid, number of columns in the grid, Sally's vertical speed, and Sally's horizontal speed, respectively.
The $$$i$$$th of the next $$$n$$$ lines contains a string of length $$$m$$$, consisting only of characters '*' and '@' — describing the $$$i$$$th row of the grid, where '*' denotes a grass cell and '@' denotes a rock cell.
The next line contains a single integer $$$q$$$ (In this version $$$q = 0$$$) — denoting the number of minutes for which rocks will fall from the sky.
The $$$j$$$th of the next $$$q$$$ lines contains two integers $$$r_j$$$ and $$$c_j$$$ ($$$1 \leq r_j \leq n$$$, $$$1 \leq c_j \leq m$$$) — denoting the row and column of which the $$$j$$$th rock will fall. It is guaranteed that the cell at row $$$r_j$$$ and column $$$c_j$$$ will be grass before the $$$j$$$th rock falls.
Output $$$q + 1$$$ space separated integers, where the $$$j$$$th integer denotes the openness of the field after the first $$$j - 1$$$ rocks have fallen onto the field.
2 2 1 1**@*0
2
3 7 1 2@@@@***@*********@@@@0
26
In preparing for the festivities, you have laid out $$$n$$$ envelopes, each containing some number of coins. You go to sleep, but two sneaky children named Ai and Bo are trying to steal some of the coins! Of course, there is some method to their madness, so they decide to play the following game.
Ai and Bo take turns, with Ai going first. On each turn, the current player must pick some non-empty subset of envelopes that currently have the same non-zero number of coins. Then, they will take 1 coin from each of the envelopes they selected. If there are no more coins in any envelope, then the game ends.
Interestingly, they don't care about the total number of coins that they each collect, but just whoever makes the final move wins. Given the number of coins in each envelope and that Ai and Bo play optimally, can you determine who wins?
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of envelopes.
The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of coins in the $$$i$$$th envelope.
Output "Ai" (without the quotes) if Ai will win the game assuming perfect strategy, and "Bo" otherwise.
21 1
Ai
12
Bo
51 2 3 4 5
Ai
41 2 2 3
Bo
In the first test case, Ai can select both envelopes containing 1 coin and win.
In the second test case, there is only one envelope with 2 coins, so Ai can only take a coin from that envelope, followed by Bo taking a coin from the envelope and winning.
This is the hard version of the problem. The difference between the versions is that in this version $$$0 \leq q \leq n \cdot m$$$.
Sally the Snake has found herself in a field of grass and rocks. The field can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Every cell in the grid is either '*' (grass) or '@' (rock).
Sally is a fast snake. Interestingly, she moves at a speed $$$k_v$$$ when moving up or down, while she moves at a speed of $$$k_h$$$ when moving left or right.
Sally is a peculiar snake, and every movement she takes must consist of the following steps:
Sally is a curious snake. She wants to know how many pairs of grass cells $$$a$$$ and $$$b$$$ there are such that $$$a \neq b$$$ and she can reach cell $$$b$$$ after some number of complete movements from cell $$$a$$$. She calls this quantity the openness of the field.
Sally is a stupid snake. She needs you to find this value for her!
Lastly, Sally is in danger for the next $$$q$$$ minutes. Each minute from $$$1$$$ to $$$q$$$, a rock will fall from the sky and land in some cell of the grid (that contained grass). The cell that the rock falls on will no longer have grass and should be considered a rock cell.
Please help Sally by finding the openness of the field before any rocks fall, as well as after each rock falls onto the grid.
The first line of input will contain four integers $$$n$$$, $$$m$$$, $$$k_v$$$, and $$$k_h$$$ ($$$2 \leq n, m \leq 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$, $$$1 \leq k_v \lt n$$$, $$$1 \leq k_h \lt m$$$) — denoting the number of rows in the grid, number of columns in the grid, Sally's vertical speed, and Sally's horizontal speed, respectively.
The $$$i$$$th of the next $$$n$$$ lines contains a string of length $$$m$$$, consisting only of characters '*' and '@' — describing the $$$i$$$th row of the grid, where '*' denotes a grass cell and '@' denotes a rock cell.
The next line contains a single integer $$$q$$$ ($$$0 \leq q \leq n \cdot m$$$) — denoting the number of minutes for which rocks will fall from the sky.
The $$$j$$$th of the next $$$q$$$ lines contains two integers $$$r_j$$$ and $$$c_j$$$ ($$$1 \leq r_j \leq n$$$, $$$1 \leq c_j \leq m$$$) — denoting the row and column of which the $$$j$$$th rock will fall. It is guaranteed that the cell at row $$$r_j$$$ and column $$$c_j$$$ will be grass before the $$$j$$$th rock falls.
Output $$$q + 1$$$ space separated integers, where the $$$j$$$th integer denotes the openness of the field after the first $$$j - 1$$$ rocks have fallen onto the field.
2 2 1 1**@*11 2
2 0
3 7 1 2@@@@***@*********@@@@32 61 51 7
26 20 6 6