ET Glob has an array of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. Unfortunately, he is unhappy with this array and, in his anger, wants to level it to the ground (i.e. make $$$a_1=a_2=\ldots = a_n=0$$$). While he could technically level the array instantly, ET Glob wants to make its death slow and painful. To achieve this, he wants to angrily touch the array. With one touch he can subtract $$$1$$$ from a particular element of the array and its neighbours. For example, if ET Glob angrily touches the third element of $$$a=\{5,6,7,8\}$$$, the array becomes $$$\{5,5,6,7\}$$$, whereas if he touches the first element, the array becomes $$$\{4,5,7,8\}$$$.
Please note that in the second example the last element remains unchanged, because it is not considered a neighbour of the first element.
You are given $$$t$$$ testcases. Each testcase contains an integer $$$n$$$ and an array $$$a$$$ of length $$$n$$$. For each testcase, ET Glob wants to know if he can flatten the array. If he can, print "YES", followed by $$$n$$$ integers, the $$$i$$$-th of which being the number of times ET Glob has to touch the $$$i$$$-th element of the array. Otherwise, simply print "NO".
The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of testcases. Each testcase consists of $$$2$$$ lines, the former containing one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$), and the latter containg $$$n$$$ integers, the elements of the array ($$$0 \le a_i \le 10^9$$$, for all $$$i \in [1,n]$$$).
It is guaranteed that the sum of all $$$n$$$ does not exceed $$$3 \cdot 10^5$$$ (i.e. $$$\sum n \le 3 \cdot 10^5$$$).For each testcase, if ET Glob can flatten the array, print "YES", without the quotes, followed by the way the array can be flattened. Otherwise, print "NO", without the quotes.
Note: Capitalization doesn't matter, YeS, yEs and yes are all recognised as a positive answer. If there are multiple valid answers, you may print any.- Subtask 1 (7 points): $$$1 \le n \le 3$$$;
- Subtask 1 (14 points): ET Glob doesn't need to touch the first element at all;
- Subtask 2 (33 points): $$$0 \le a_i \le 100$$$;
- Subtask 3 (46 points): No further constraints.
6 8 5 6 8 7 9 8 9 6 2 5 6 1 7 7 3 6 4 5 6 7 5 3 8 8 0 9 5 9 6 8 8 10 7 5 4
YES 0 5 1 2 4 3 1 5 NO YES 7 YES 2 1 3 0 2 4 1 YES 8 0 0 NO
Tot tresarind, tot asteptând...
Sunt singur, si mă duce-un gând
Spre locuintele lacustre.
Si orice asemanare din continutul de mai jos cu persoane reale este pur intamplatoare
All are old and all renewed, except for the recent increase in taxes. Nelu, unable to change his financial situation, has to deal with the following problem:
Nelu has $$$N$$$ wet laundry items that he would like to dry off by placing them on the heater in his flat. Each laundry item is characterized by three integers $$$x_i$$$ — where on the heater Nelu will place this item, $$$c_i$$$ — the amount of water contained in that item. and $$$t_i$$$ — the moment when Nelu will place that item on the heater.
After placing a laundry item on the heater at time $$$t_i$$$, vapors will start to form above it for the next $$$c_i$$$ seconds, indicating that the drying process is effective (a.k.a. Danut Nicolae wasn't harsh enough on the tax reforms). More formally, for every second $$$T \in [t_i,t_i+c_i-1]$$$, all the previous vapors would rise up by $$$1$$$ height unit, and a new vapor will form just above the laundry item at $$$1$$$ height unit.
After all vapors have been realeased, they will continue their course towards the ceiling at $$$H$$$ height units above the heater. Consequently, a vapor generated at time $$$T$$$ will reach altitude $$$Y$$$ at time $$$Y+T$$$.
Unfortunately for Nelu, some safety measures were implemented in his flat so the ceiling won't become as yellow as his teeth. Fortunately for Nelu, the safety features are $$$M$$$ sponges on his wall. For each sponge, the following are also known:
- its position relative to the heater (i.e. its X-coordinate), denoted with $$$x_i$$$
- the height above the heater at which it is placed (i.e. the Y-coordinate in the afferent xOy plane, where the Ox line is the heater), denoted with $$$y_i$$$
- the maximum amount of water/vapor that sponge can retain, denoted with $$$w_i$$$. After a sponge exceeds its maximum capacity, it will fall onto the floor and be never heard from again.
When some vapor reaches the exact position of a sponge, that sponge will lose $$$1$$$ unit of water from its capacity. After the sponge absorbs $$$w_i$$$ vapors, the sponge will fall, and all subsequent vapors will continue rising to the ceiling.
Once $$$W$$$ vapors reach the ceiling, the latter will form a hole, similar to those on Nelu's morals, creating a liability to the structural integrity of the building. To prevent this, the administrator has decided calculate at which time the building would collapse. But because Nelu is very unpredictable, he will add $$$Q$$$ elements in the configuration, and after each and one of these he wants to know at what time he should evacuate the building. But since this is very hard, he is asking you to do this while he is booking a flight to Cancun.
The first line of input contains five integers: $$$N$$$ ($$$1\le N \le 10^5$$$) — the number of laundry items, $$$M$$$ ($$$1\le M \le 10^5$$$) — the number of initial sponges, $$$Q$$$ ($$$1\le Q \le 10^5$$$)— the number of new items, $$$W$$$ ($$$1 \le W \le 10^9$$$) — the number of vapors required to break the ceiling, and $$$H$$$ ($$$1\le H \le 5 \cdot 10^5$$$) — the height of the ceiling.
On the following $$$N$$$ lines, it will be described by $$$x_i$$$, $$$c_i$$$, $$$t_i$$$, the parameters of the i-th sock that will appear initially on the heater.
On the following $$$M$$$ lines, it will be described by $$$x_i$$$, $$$y_i$$$, $$$w_i$$$, the parameters of the i-th sponge that will appear initially on the heater.
On the following $$$Q$$$ lines, there will be four numbers. The first of them will be $$$type_i$$$, denoting the type of the update. If $$$type_i = 1$$$, then the following numbers will describe a sock by $$$x_i, c_i, t_i$$$. Otherwise, the following numbers will describe a sponge by $$$x_i, y_i, w_i$$$.
For every sock (including one from a query), $$$1 \le x_i, c_i, t_i \le 10^5$$$
For every sponge (including one from a query), $$$1 \le x_i \le 10^5, 1 \le y_i \lt H, 1 \le w_i \le 10^5$$$
On the first line of output there should be printed the answer for the After each new item is added to the configuration, print one integer: the number of seconds before the ceiling of Nelu's flat would form holes. In the case when the building would never collapse, it should be printed -1
| Group | Add. constraints | Points | Req. groups |
| $$$1$$$ | $$$ N, M \le 1\,000, Q \le 2\,000, x_i \le 1\,000, c_i \textrm{ or } t_i \le 1\,000 , H \le 50\,000$$$ | $$$6$$$ | – |
| $$$2$$$ | $$$ N, M \le 10\,000, Q \le 30\,000, x_i \le 20\,000, c_i \textrm{ or } t_i \le 20\,000 , H \le 50\,000$$$ | $$$34$$$ | 1 |
| $$$3$$$ | $$$ N, M \le 100\,000, Q = 0, x_i \le 100\,000, c_i \textrm{ or } t_i \le 100\,000 , H \le 500\,000$$$ | $$$5$$$ | – |
| $$$4$$$ | $$$ N, M \le 100\,000, Q \le 100\,000, \textrm{max}(x_i) \cdot \textrm{max}(c_i + t_i) \le 1\,000\,000, x_i \le 100\,000, c_i \textrm{ or } t_i \le 100\,000, H \le 500\,000$$$ | $$$26$$$ | – |
| $$$5$$$ | — | $$$29$$$ | $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ |
4 5 4 1 10 1 3 5 2 7 4 3 4 7 4 1 3 1 4 4 2 3 3 3 8 4 2 5 1 4 6 1 2 2 5 6 1 4 1 18 1 3 5 5 1 1 3 1
18 -1 28 18 16
At the beggining, the hole will form at the position with X-coordinate = 2. The vapors generated at position 2 at the seconds 4, 5, 6 will be retained in the first sponge at the seconds 7, 8, 9, thus at time $$$T = 9$$$ the first sponge will fall. Then, the vapor generated at the second 7 will be retained in the second sponge at the seconds 12, thus at time $$$T = 12$$$ the second sponge will fall. The vapor formed at the second 8 will not have any other sponge in its way (since all the vapors generated before him filled all the sponges in its way), so at time $$$T = 18$$$, the vapor will be retained in the ceiling, and the building will collapse. We leave as an exercise to the reader the explication for the following queries
The Romanian word "popeală" has its origins in a Romanian historical novella, "Alexandru Lăpușneanul", where the eponymous Prince of Moldavia uses a variation of the term to describe his upcoming revenge on his usurpers. The term was recently revived, somewhat surprisingly, in the Romanian programming contest scene. It's used to describe any situation in which the scientific committee makes life harder for the contestants in an unorthodox and (usually) involuntary way: very strict time limits, invalid test cases, wrong statements,wrong statements, stealing keyboards and other such mechanisms. This task is about such a "popeală". Source : CEOI 2016 , Romania
GrandPaPà is very upset that nobody liked his problems in the past InfoLeague™ contest. He wants to take revenge for that **insert Pablo Escobar**. He gives you nicely throws you number N. He then asks you nicely orders you to find the number of permutations of length N such that the maximum size of a subsequence ( contiguous indices ) that only has consecutive values is exactly equal to K. For example , [1, 2, 3, 4] would satisfy K = 4 ( [1, 4] is the best subsequence ) while [3, 1, 2, 4] will satisfy K = 2 ( [2, 3] is the best subsequence ). If you can solve this task , GrandPaPà will be happy once again. Else he will **redacted**.
The input consists of two integers N (1 ≤ N ≤ 2000) — the length of the permutations, and MOD (1 ≤ MOD ≤ 109) — the modulo used to compute the answer.
The output consists of N integers , the number of permutations which hold the propriety for every K in the set {1,2,3...,N}. This means you need to solve the problem for every possible K and print the answers. Since the answers may be very large, print them modulo MOD.
- For all test data , 1 ≤ N ≤ 2000 , 1 ≤ MOD ≤ 109.
- For 10 points , 1 ≤ N ≤ 11.
- For another 50 points , 11 < N ≤ 500.
- For the remaining 40 points , there are no further restrictions.
- MOD may not be a prime number !!!
3 666013
3 2 1
Let's look at all the permutations of length 3.
- [1,2,3] => K = 3 ( sequence [1,3] is consisting of consecutive values and has maximal length 3 )
- [1,3,2] => K = 1 ( sequences [1,1],[2,2],[3,3] are consisting of consecutive values and have maximal length 1)
- [2,1,3] => K = 1 ( sequences [1,1],[2,2],[3,3] are consecutive and have maximal length 1)
- [2,3,1] => k = 2 ( sequence [1,2] is consisting of consecutive values and has maximal length 2 )
- [3,1,2] => k = 2 ( sequence [2,3] is consisting of consecutive values and has maximal length 2 )
- [3,2,1] => k = 1 ( sequences [1,1],[2,2],[3,3] are consecutive and have maximal length 1)
Thus , we need to print [3 mod 666013 , 2 mod 666013 , 1 mod 666013] = [3,2,1].