Avatar aang is in trouble. He's facing a threat bigger than anything he has faced before and he needs the help of former avatars. However talking with his pasts lives, is exhausting so he wants your help to find the correct avatars to contact.
You are given an array $$$a_1,a_2,\ldots,a_n$$$ where $$$a_i$$$ is how helpful the $$$i$$$-th avatar is, and $$$a_n$$$ avatar is the latest avatar before Aang. Consider that an avatar could be unhelpful rather than helpful, so he'll have a negative value.
You'll have to answer $$$q$$$ queries, consisting of a number $$$x$$$ indicating, Aang doesn't want to go further back than the $$$x$$$-th avatar. So starting from avatar $$$x+1$$$, find the maximum possible sum of helpfuness a contiguous subarray of avatars can give. Tradition indicates that Aang must recieve help from at least 1 avatar.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2\cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
Each of the next $$$q$$$ lines contains one integer $$$x$$$ ($$$0 \le x \lt n$$$).
For each query, print the maximum help Aang can get, even if it is negative.
5 4-2 3 -1 4 -50134
6 6 4 -5
For $$$x=0$$$, all avatars are available. For $$$x=n-1$$$, the only available avatar is $$$a_n$$$.
The kingdom has $$$n$$$ cities. Travel is represented by a directed cost matrix $$$M$$$: if $$$M[i][j]=-1$$$, travelling directly from city $$$i$$$ to city $$$j$$$ is impossible; otherwise $$$M[i][j]$$$ is its non-negative toll. The matrix need not be symmetric. Also, $$$M[i][i]=0$$$.
Then $$$m$$$ meteor updates occur. An update gives two cells $$$(i,j)$$$ and $$$(x,y)$$$ and an increment $$$k$$$. It adds $$$k$$$ to every existing off-diagonal entry in the axis-aligned rectangle whose row range is $$$[\min(i,x),\max(i,x)]$$$ and column range is $$$[\min(j,y),\max(j,y)]$$$. Entries equal to $$$-1$$$ remain $$$-1$$$, and diagonal entries remain $$$0$$$.
After all updates, answer $$$q$$$ minimum-cost directed-path queries. For each pair $$$(a,b)$$$, output the minimum total toll from $$$a$$$ to $$$b$$$, or $$$-1$$$ if no directed path exists.
The first line contains $$$n$$$ ($$$1 \le n \le 750$$$). Each of the next $$$n$$$ lines contains $$$n$$$ integers $$$M[i][j]$$$ ($$$-1 \le M[i][j] \le 10^6$$$). The diagonal entries are $$$0$$$; $$$-1$$$ denotes no directed edge.
The next line contains $$$m$$$ ($$$0 \le m \le 10^5$$$). Each of the next $$$m$$$ lines contains $$$i,j,x,y,k$$$ ($$$1 \le i,j,x,y \le n$$$, $$$0 \le k \le 10^9$$$), describing an update as above.
The next line contains $$$q$$$ ($$$1 \le q \le 10^5$$$). Each of the next $$$q$$$ lines contains $$$a,b$$$ ($$$1 \le a,b \le n$$$).
Print $$$q$$$ lines. The $$$t$$$-th line must contain the minimum cost of a directed path for the $$$t$$$-th query after all updates, or $$$-1$$$ if no such path exists.
30 2 -12 0 4-1 1 011 1 2 2 331 22 31 3
5 4 9
Updates affect matrix entries, not already-computed shortest paths. A missing edge ($$$-1$$$) is never created by an update. A query from a city to itself has answer $$$0$$$. All final answers fit in a signed 64-bit integer.
There are $$$n$$$ vertices connected by $$$n-1$$$ roads. Ignoring direction, the roads form a tree.
For every road, traveling in its two directions may have different costs. An input line $$$u\ v\ a\ b$$$ means that traveling from $$$u$$$ to $$$v$$$ costs $$$a$$$, while traveling from $$$v$$$ to $$$u$$$ costs $$$b$$$.
For every possible starting vertex $$$r$$$, find the sum of the costs of the unique directed trips from $$$r$$$ to all vertices. The trip from $$$r$$$ to itself has cost zero.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$).
Each of the next $$$n-1$$$ lines contains four integers $$$u$$$, $$$v$$$, $$$a$$$, and $$$b$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$, $$$1 \le a,b \le 10^6$$$). The undirected edges $$$(u,v)$$$ form a tree. The costs of directions $$$u\to v$$$ and $$$v\to u$$$ are $$$a$$$ and $$$b$$$, respectively.
Print $$$n$$$ integers. The $$$r$$$-th integer must be the sum of travel costs from vertex $$$r$$$ to every vertex.
1
0
31 2 4 72 3 2 5
10 9 17
42 1 3 82 3 4 64 2 5 2
30 9 23 22
All required sums fit in signed 64-bit integers.
Revachol, Jamrock, Precinct 41. The body still hangs behind the Whirling-in-Rags, and the RCM demands paperwork.
Your evidence ledger has $$$N$$$ entries, each stamped with a non-negative case number. Logic points out the obvious: the Coalition's clerks do not read your report — they only measure its Completeness Index, defined as the smallest non-negative integer that does not appear among the case numbers in the ledger. The higher the index, the more thorough you appear.
Inland Empire whispers that ink is negotiable. You may overwrite the case number of at most $$$K$$$ entries, replacing each with any non-negative integer you like. You cannot add entries and you cannot tear any out — Kim would notice.
Determine the maximum Completeness Index your ledger can attain.
The first line contains two integers $$$N$$$ and $$$K$$$ $$$(1 \le N \le 2 \cdot 10^5$$$, $$$0 \le K \le N)$$$ — the number of entries in the ledger and the number of entries you may overwrite.
The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ $$$(0 \le a_i \le 10^9)$$$, where $$$a_i$$$ is the case number stamped on the $$$i$$$-th entry.
Print a single integer: the maximum Completeness Index achievable by overwriting at most $$$K$$$ entries.
6 20 2 3 7 1 9
6
4 15 5 5 5
1
The Completeness Index of a collection of non-negative integers is the smallest non-negative integer absent from it. For example, the index of $$$\{0, 1, 3\}$$$ is $$$2$$$, the index of $$$\{1, 2\}$$$ is $$$0$$$, and the index of $$$\{\}$$$ is $$$0$$$.
Thanos has an array whose length is a power of two. Before he sees it, every element is chosen independently and uniformly from the integers $$$1,2,\ldots,K$$$.
An array is sorted if it is nondecreasing. While the current array is not sorted, Thanos performs a snap:
- with probability $$$1/2$$$, he keeps the left half and discards the right half;
- with probability $$$1/2$$$, he keeps the right half and discards the left half.
All snap choices are independent of each other and of the initial array. After each snap, he checks the remaining array again. An array of length one is always sorted.
The initial length is $$$N=2^n$$$. Find the expected number of snaps, where the expectation is taken over both the random initial array and all snap choices.
The only line contains two integers $$$n$$$ and $$$K$$$ – the exponent of the initial length and the number of possible values. The value of $$$n$$$ is between 0 and 200000, inclusive, and $$$K$$$ is between 1 and 200000, inclusive.
It is guaranteed that $$$nK$$$ is at most 20000000.
Let the expected number of snaps be the rational number $$$p/q$$$, where $$$p$$$ and $$$q$$$ are coprime. Print the residue modulo 998244353 of the product of $$$p$$$ and $$$q^{-1}$$$, where $$$q^{-1}$$$ is the multiplicative inverse of $$$q$$$ modulo 998244353. It is guaranteed that this inverse exists.
1 2
748683265
0 1
0
4 5
280149939
For $$$n=1$$$ and $$$K=2$$$, the only unsorted initial array is $$$[2,1]$$$. It requires one snap, so the expectation is $$$1/4$$$.
The training committee keeps its $$$n$$$ contestants in a single mentoring tree. Contestant $$$1$$$ is the head coach, and every other contestant $$$i$$$ is mentored by exactly one contestant $$$p_i$$$. Contestant $$$i$$$ has solved $$$a_i$$$ problems so far.
The team of a contestant $$$u$$$ is $$$u$$$ together with everybody whose chain of mentors passes through $$$u$$$: the contestants mentored by $$$u$$$, the ones mentored by those, and so on. Every contestant belongs to their own team.
The season is long and the committee keeps rearranging the tree. There are $$$q$$$ events, each of one of four kinds.
- $$$1\ u\ v$$$: contestant $$$u$$$ is reassigned to be mentored by contestant $$$v$$$, and the whole team of $$$u$$$ moves along. If $$$v$$$ belongs to the team of $$$u$$$, the reassignment would put a contestant above their own mentor, so the committee rejects the request and nothing changes; the same happens when $$$u$$$ and $$$v$$$ are the same contestant.
- $$$2\ u\ x$$$: every member of the team of $$$u$$$ solves $$$x$$$ additional problems.
- $$$3\ u$$$: report how many problems the team of $$$u$$$ has solved in total.
- $$$4\ u$$$: the mentoring distance of a member $$$w$$$ of the team of $$$u$$$ is the number of mentoring links that lead from $$$w$$$ up to $$$u$$$. Report the sum of the mentoring distances of every member of the team of $$$u$$$.
In the last two events $$$u$$$ counts as a member of its own team, contributing $$$a_u$$$ problems and a mentoring distance of $$$0$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of contestants and the number of events.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the problems each contestant has already solved.
The third line contains $$$n-1$$$ integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — the mentor of each contestant other than the head coach. The mentoring links form a rooted tree: following mentors from any contestant reaches contestant $$$1$$$. A mentor may have a larger index than the contestant they mentor. This line is empty when $$$n = 1$$$.
Each of the next $$$q$$$ lines describes one event and starts with its kind.
- 1 u v ($$$1 \le u,v \le n$$$) — reassign contestant $$$u$$$ to mentor $$$v$$$.
- 2 u x ($$$1 \le u \le n$$$, $$$1 \le x \le 10^6$$$) — everyone in the team of $$$u$$$ solves $$$x$$$ more problems.
- 3 u ($$$1 \le u \le n$$$) — total problems solved by the team of $$$u$$$.
- 4 u ($$$1 \le u \le n$$$) — total mentoring distance inside the team of $$$u$$$.
For every event of kind $$$3$$$ or $$$4$$$, print one line with the requested value, in the same order as the events appear in the input.
The answers can exceed $$$2^{31}$$$. They are compared as a sequence of integers.
7 610 20 30 40 50 60 701 1 1 2 2 43 24 12 2 53 21 2 44 1
130 9 145 12
5 61 2 3 4 51 1 2 21 2 54 12 2 103 11 2 34 1
6 45 9
3 45 5 51 24 11 3 14 13 3
3 2 5
There are $$$n$$$ cities and $$$m$$$ proposed undirected railway tracks. The cities are numbered from $$$1$$$ to $$$n$$$, and the tracks are numbered from $$$1$$$ to $$$m$$$ in input order. Each track has one of $$$n-1$$$ permit colors, numbered from $$$1$$$ to $$$n-1$$$.
Choose exactly $$$n-1$$$ distinct tracks such that they form a spanning tree and every permit color is used exactly once. A spanning tree is a connected, acyclic graph containing all $$$n$$$ cities.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 120$$$, $$$n-1 \le m \le 2500$$$).
Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$c$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$, $$$1 \le c \lt n$$$), describing an undirected track between cities $$$u$$$ and $$$v$$$ with permit color $$$c$$$.
Parallel tracks are allowed, even with the same endpoints, provided that no two input lines describe the same unordered pair of endpoints with the same color. Every color from $$$1$$$ to $$$n-1$$$ occurs in at least one track.
If no valid selection exists, print $$$-1$$$.
Otherwise, print $$$n-1$$$ distinct integers: the indices of tracks in any valid selection, in any order. Any valid answer is accepted.
4 51 2 12 3 23 4 31 3 12 4 2
1 2 3
The selected tracks must satisfy both requirements simultaneously: they must connect all cities without a cycle, and their colors must be pairwise distinct. Because there are exactly $$$n-1$$$ selected tracks and exactly $$$n-1$$$ colors, pairwise distinct colors are equivalent to using every color exactly once.
Word has reached House Hlaalu of a merchant blessed with a satchel of Almsivi Intervention scrolls — the Tribunal's gift that lets one step instantly to the nearest temple anywhere on Vvardenfell. No longer bound to the silt strider's fixed path, the merchant may appear at any settlement, in any order, to trade raw ebony.
At each of the $$$N$$$ settlements, the price of raw ebony is known. The merchant will buy one unit at a settlement and sell it at a (possibly identical) settlement. Since travel order is unrestricted, the maximum profit is the largest selling price minus the smallest buying price. If all prices are equal, the answer is $$$0$$$.
Given the prices at all $$$N$$$ settlements, determine the maximum profit the merchant can achieve.
The first line contains a single integer $$$N$$$ $$$(2 \le N \le 2 \cdot 10^5)$$$, the number of settlements on Vvardenfell where raw ebony is traded.
The second line contains $$$N$$$ integers $$$p_1, p_2, \ldots, p_N$$$ $$$(1 \le p_i \le 10^9)$$$, where $$$p_i$$$ is the price of one unit of raw ebony at the $$$i$$$-th settlement.
Print a single integer: the maximum profit the merchant can achieve.
57 1 5 3 6
6
310 10 10
0
You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ has a positive integer weight $$$a_i$$$.
You want to choose positive integers $$$b_1, b_2, \dots, b_n$$$.
Each edge of the tree contains one of the characters <, =, or >. If an edge is written as $$$u\ v\ c$$$, then:
- if $$$c \text{ is equal to } \lt $$$, you must have $$$b_u \lt b_v$$$;
- if $$$c \text{ is equal to } =$$$, you must have $$$b_u = b_v$$$;
- if $$$c \text{ is equal to } \gt $$$, you must have $$$b_u \gt b_v$$$.
Among all valid assignments, minimize $$$$$$ a_1 b_1 + a_2 b_2 + \dots + a_n b_n. $$$$$$
For the given constraints, it can be proved that the optimal assignment is unique.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200'000$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1'000'000$$$).
Each of the next $$$n - 1$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ and one character $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$, $$$c_i$$$ is one of <, =, >), meaning that the tree contains an edge between $$$u_i$$$ and $$$v_i$$$, and the required relation is $$$b_{u_i}\ c_i\ b_{v_i}$$$.
Print the minimum possible value of $$$$$$ a_1 b_1 + a_2 b_2 + \dots + a_n b_n $$$$$$ in the first line.
In the second line, print the unique optimal assignment $$$b_1, b_2, \dots, b_n$$$.
It can be proved that, for the given constraints, the minimum value always fits in a signed $$$64$$$-bit integer.
65 1 4 3 2 61 2 <2 3 >2 4 <4 5 =4 6 >
32 1 2 1 3 3 1
79 2 8 1 7 3 61 2 =2 3 <3 4 >2 5 =5 6 <5 7 >
76 2 2 3 1 2 3 1
The first sample requires:
- $$$b_1 \lt b_2$$$,
- $$$b_2 \gt b_3$$$,
- $$$b_2 \lt b_4$$$,
- $$$b_4 = b_5$$$,
- $$$b_4 \gt b_6$$$.
One optimal assignment is $$$1\ 2\ 1\ 3\ 3\ 1$$$, and its cost is $$$$$$ 5 \cdot 1 + 1 \cdot 2 + 4 \cdot 1 + 3 \cdot 3 + 2 \cdot 3 + 6 \cdot 1 = 32. $$$$$$
Etienne and Christian are organizing a Sunday event along Avenida Vallarta, modeled as a straight line. Participant $$$i$$$ waits at coordinate $$$x_i$$$.
They must place exactly $$$k$$$ hydration stations. Each station may be placed at any real coordinate, and multiple stations may be placed at the same coordinate. After the stations are placed, each participant walks to a station minimizing the absolute distance from their position. If several stations are equally near, choosing any of them gives the same walking distance.
Find the minimum possible sum of the walking distances of all participants.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100000$$$, $$$k \le 25$$$).
The second line contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$0 \le x_1 \le x_2 \le \cdots \le x_n \le 10^9$$$). Equal coordinates are allowed.
Print one integer: the minimum possible total walking distance.
Although station coordinates may be real numbers, an optimal solution can place every station at a participant coordinate, so the answer is an integer. The answer fits in a signed 64-bit integer but may exceed the 32-bit range.
6 30 2 3 10 11 20
4
In the sample, stations can be placed at coordinates $$$2$$$, $$$10$$$, and $$$20$$$. The walking distances are $$$2,0,1,0,1,0$$$, for a total of $$$4$$$.
Requiring exactly $$$k$$$ stations never increases the optimum: any redundant station may be placed at the same coordinate as another station.
An artisan paints a mural using $$$n$$$ axis-aligned rectangular stencils. Rectangle $$$i$$$ is the half-open set $$$[x_{1,i},x_{2,i}) \times [y_{1,i},y_{2,i})$$$. Rectangles may overlap, share boundary segments, or coincide.
A point is covered exactly once if it belongs to exactly one rectangle. The union consists of all points covered by at least one rectangle. Its perimeter is the total length of the boundary separating covered points from uncovered points; shared boundaries inside the union do not contribute.
Find (1) the area covered exactly once and (2) the perimeter of the union.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 200000$$$).
Each of the next $$$n$$$ lines contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, and $$$y_2$$$ describing one rectangle ($$$-10^9 \le x_1 \lt x_2 \le 10^9$$$ and $$$-10^9 \le y_1 \lt y_2 \le 10^9$$$).
Print two integers: the total area covered by exactly one rectangle and the perimeter of the union, in that order.
Both values fit in a signed 64-bit integer but may exceed the signed 32-bit range.
20 0 2 21 0 3 1
4 10
Rectangles are half-open only to make point membership unambiguous. Changing which rectangle owns a shared boundary does not change either requested value. Use 64-bit integer arithmetic.
In the ruined observatory above the dead city, Racso and Christian copy out the Ledger of True Names.
A true name is power: speak one and the thing it belongs to must answer. But a name spoken alone burns the speaker, so the old sorcerers bound names in pairs, sealing each pair under a single sigil. The binding holds only if the two names begin the same way, and the sigil's power is exactly the length of that shared beginning.
The brothers have $$$N$$$ true names before them and one night of candlelight. Find the power of the strongest sigil they can seal — the longest beginning shared by two different names in the Ledger.
The first line contains a single integer $$$N$$$ $$$(2 \le N \le 10^5)$$$ — the number of true names in the Ledger.
Each of the next $$$N$$$ lines contains one true name $$$s_i$$$, a non-empty string of lowercase Latin letters with $$$|s_i| \le 50$$$.
It is guaranteed that the sum of $$$|s_i|$$$ over all names does not exceed $$$10^5$$$. Names are not necessarily distinct.
Print a single integer: the power of the strongest sigil, or $$$0$$$ if no two names in the Ledger even begin with the same letter.
5racsorascalchristianchristchris
6
3umbraumbrasol
5
Two names $$$s$$$ and $$$t$$$ share a beginning of length $$$\ell$$$ if $$$s_1 = t_1$$$, $$$s_2 = t_2$$$, $$$\ldots$$$, $$$s_\ell = t_\ell$$$.
Two entries of the Ledger are always considered different if they sit at different positions in the input, even when their names are identical: two entries reading umbra share a beginning of length $$$5$$$.
Miguel organized a chess tournament with $$$n$$$ participants numbered from $$$1$$$ to $$$n$$$. Every pair played exactly one game. Every game ended with one winner and one loser; there were no draws.
Everything was going well until the software recording the results broke down. The individual game results disappeared, and only a table of totals could be recovered: according to it, participant $$$i$$$ earned exactly $$$b_i$$$ victories.
Miguel and the participants do not trust this table. If the program lost the games, who can guarantee that the totals were not corrupted too? Before announcing the winner, Miguel wants to know whether those numbers could describe a tournament like the one they organized.
Determine whether there is a set of game results consistent with the recovered totals. If there is, reconstruct one. You do not need to recover the original games: any reconstruction in which each participant $$$i$$$ won exactly $$$b_i$$$ times is acceptable.
The first line contains an integer $$$n$$$ ($$$1\le n\le2000$$$).
The second line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0\le b_i\le n-1$$$): the recorded number of victories for each participant.
If no valid reconstruction exists, print NO.
Otherwise, print YES, followed by $$$n$$$ lines, each containing a string of exactly $$$n$$$ characters, all either 0 or 1, without spaces. These strings form a matrix $$$A$$$, where $$$A_{i,j}=1$$$ means that participant $$$i$$$ defeated participant $$$j$$$.
The matrix must satisfy $$$A_{i,i}=0$$$, $$$A_{i,j}+A_{j,i}=1$$$ for all $$$i\ne j$$$, and $$$\sum_{j=1}^{n}A_{i,j}=b_i$$$ for every $$$i$$$. If several valid reconstructions exist, print any of them.
40 0 3 3
NO
10
YES 0
32 0 1
YES 011 000 010
Deep beneath the frost of Hjaalmarch, the excavation at Ustengrav has unearthed the collapsed remains of ancient Nord burial cairns — stone monuments the old draugr-lords raised over their fallen thanes.
The Nords built every cairn the same way: the topmost layer holds a single stone, and each layer beneath it holds exactly one stone more than the layer above. A pile of stones is called cairn-perfect if its stones can be arranged into such a cairn, using every stone and leaving no layer unfinished. Equivalently, a positive integer is cairn-perfect exactly when it is a triangular number $$$$$$T_k=1+2+\cdots+k=\frac{k(k+1)}{2}$$$$$$ for some integer $$$k\ge 1$$$.
Urag gro-Shub, keeper of the Arcanaeum at the College of Winterhold, has grown impatient with the excavation ledgers. The diggers record only the number of stones in each rubble heap, never its shape, and Urag will authorise no further shipment until he knows how many of the recorded counts could possibly have been complete cairns.
Given two integers $$$L$$$ and $$$R$$$, determine how many integers $$$n$$$ with $$$L \le n \le R$$$ are cairn-perfect.
The single line of input contains two integers $$$L$$$ and $$$R$$$ $$$(1 \le L \lt R \le 10^{12})$$$, the smallest and largest stone-counts recorded in the excavation ledger. Both bounds are inclusive.
Print a single integer: the number of cairn-perfect stone-counts in the ledger's range.
1 10
4
6 9
1