Just BFS over $$$(x, y, time)$$$ pairs, the clouds all leave after at most $$$100$$$ so the answer is small and you can just do whatever.

Work with the prefix sum array $$$s_0, s_1, \dots, s_n$$$ so you add $$$x$$$ to some suffix and the happiness is the number of subsegments $$$s[l..r]$$$ such that $$$l < r$$$ and $$$\min(s[l..r]) = s[l]$$$. For each index $$$l$$$ compute the smallest $$$f(l) > l$$$ such that $$$s_{f(l)} < s_l$$$, so the number of segments that start at $$$s_l$$$ is exactly $$$f(l) - l$$$ unless the suffix you add $$$x$$$ to starts at some $$$i$$$ with $$$l < i \le f(i)$$$. Sweep the starting point from right to left and keep the answer updated, you can do this with a treap.

$$$2^k > 1 + 2 + 4 + \dots + 2^{k - 1}$$$ so $$$A$$$ always gets $$$n$$$ and $$$B$$$ always gets $$$n - 1$$$, then $$$B$$$ can get anything else that's in the same connected component as $$$n - 1$$$ if you delete $$$n$$$ and nothing else.

Compute the cost of placing each odd-indexed city in each feasible position and then run min cost matching.

Notice that if you start on Monday, Wednesday or Friday then you get back to the same position after 91 days, then just simulate.

Turns out it's impossible if and only if there are two pairs of points with endpoints on the border that are arranged like $$$A, B, A, B$$$, so it reduces to checking if some pair of intervals intersects which is easy.

Just code it lol

Iterate over the number of easygoing people that end up seating next to another easygoing person. Once you fix this the entire rest of the process is fixed and you can compute the total happiness easily, and computing the probability is easy math.

Assuming you start at time $$$0$$$ doing the tasks greedily by increasing order of deadline works. Then you can check if you can place a certain task at the start in $$$O(1)$$$ by using some prefix maximums. Then just delete the smallest task you can place and recurse.

5 5 6 5
1
N 8
5 6
10 6
10 3
5 3
5 4
6 4
6 5
5 5

3 3 4 3
1
E 4
2 4
3 4
3 2
2 2

Correct answer: 1

get the prefix sum, for every $$$i$$$ count $$$sum[i]$$$, then the anser is the number of pairs $$$[l,r]$$$ such that $$$sum[l-1] = min(sum[l-1]......sum[r])$$$ ,so we get the the nxt[i] which means the first position that $$$sum[nxt[i]]<sum[i-1]$$$ && $$$nxt[i]>=i$$$, and we get the anser that ignoring the x

we add x on position p, we will affect the i that $$$nxt[i]>=p$$$ && $$$i-1<=p$$$,wo when we iterate form $$$n$$$ to $$$1$$$,when we enter $$$nxt[i]$$$,we modify the contribution of $$$i$$$,and when we leave $$$i$$$,we also modify the contribution of $$$i$$$, then we get a corrct solution when $$$x > 0$$$ because when we add $$$x$$$ on $$$p(p<=nxt[i])$$$,the first position $$$nxt[i]$$$ will only move from left to right

but when $$$x<0$$$ the $$$nxt[i]$$$ will move from right to left,we should modify all $$$i$$$'s $$$nxt[i]$$$ to $$$p$$$ such that $$$sum[i-1]>sum[p]+x$$$ ,I don't know the easy way to do this, I use a segment tree to get the $$$nxt$$$ array and another segment tree to modify the $$$nxt$$$ array

let $$$F[l][r][0/1]$$$ be the min cost when we start from $$$l/r$$$ $$$F[l][r][0] = min(max(F[l][k][1],F[k][r][0])+D[k]+dist[k])-dist[l]$$$ when iterate k from $$$l$$$ to $$$r$$$ there will exist a $$$p$$$ such that

• $$$k$$$ in $$$[l,p]$$$ $$$F[k][r][0]>F[l][k][1]$$$
• $$$k$$$ in $$$[p+1,r]$$$ $$$F[k][r][0]<F[l][k][1]$$$

we can do binary seach to get $$$p$$$,when $$$k$$$ in $$$[p+1,k]$$$,we should get the min $$$F[l][k][1]+D[k]+dist[k]$$$

we can use a segment tree to do this

for a tree of size $$$x$$$, we iterate its factor $$$p$$$,and devide it into $$$x/p$$$ blocks(only one way),each block's value is $$$val$$$, and count the number of tree $$$y$$$ and its value equal to $$$val$$$

To find the maximum sum, first sort arrays $$$F$$$ and $$$C$$$ in non-decreasing order. When $$$k=N$$$, the answer is $$$\sum_{i=1}^{N}F[i]×C[i]$$$.

For $$$k<N$$$, sum the pairs $$$F[i]×C[i]$$$ with the greatest positive product value. If there are less than $$$k$$$ such pairs (let's say $$$r$$$), sum those $$$r$$$ pairs, then take the $$$k-r$$$ remaining elements in $$$F$$$ and $$$G$$$ with the smallest absolute values, and multiply them in non-decreasing order. You can do this part in $$$O(nlogn)$$$ using FFT.

To find the minimum sum, multiply by $$$-1$$$ the elements in one of the arrays and do the same as above.