You are given $$$t$$$ test cases. For each test case, you are given two integers $$$a$$$ and $$$b$$$ ($$$a \lt b$$$), and $$$n$$$ available operations.
The $$$i$$$-th operation is described by a pair $$$(x_i, y_i)$$$:
- If $$$x_i = 1$$$, then applying this operation changes the current value $$$v$$$ to $$$v + 1$$$.
- If $$$x_i = 2$$$, then applying this operation changes the current value $$$v$$$ to $$$2v$$$.
- Applying operation $$$i$$$ costs $$$y_i$$$.
Initially, $$$v = a$$$.
You may apply each operation at most once, in any order. You may only apply an operation if after applying it the value does not exceed $$$b$$$ (i.e., you must keep $$$v \le b$$$ at all times).
Your task is to find the minimum total cost needed to reach exactly $$$v = b$$$. If it is impossible, output $$$-1$$$.
- The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
- Each test case starts with a line containing three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a \lt b \le 10^9$$$).
- The next line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$x_i \in {1,2}$$$) — the types of the operations.
- The next line contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i \le 10^9$$$) — the costs of the operations.
- It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print one integer: the minimum total cost to reach $$$b$$$, or $$$-1$$$ if it is impossible.
24 3 102 1 1 12 5 1 12 1 52 23 4
4-1
In the first test case, the cheapest way is to use two cheap $$$+1$$$ operations first, then double: $$$3 \to 4 \to 5 \to 10$$$, with total cost $$$1+1+2=4$$$.
In the second test case, only doubling operations are available, so from $$$1$$$ we can reach only $$$2$$$ and $$$4$$$, but never $$$5$$$. Hence the answers are $$$\texttt{4}$$$ and $$$\texttt{-1}$$$.
Donkey has a binary string $$$s$$$ of length $$$n$$$ (each $$$s_i \in \{0,1\}$$$). Positions are indexed from $$$0$$$ to $$$n-1$$$. He also has an energy limit $$$E$$$, an integer $$$k$$$, and an integer $$$m$$$.
Donkey starts at position $$$p = 0$$$ and may perform the following actions in any order:
- Move: choose any position $$$q$$$ ($$$0 \le q \le n-1$$$) and move from $$$p$$$ to $$$q$$$. This costs $$$|p-q|$$$ energy, and then $$$p$$$ becomes $$$q$$$.
- Toggle: if $$$p+k \lt n$$$, he may toggle both $$$s_p$$$ and $$$s_{p+k}$$$. If the value to be toggled was $$$0$$$, it becomes $$$1$$$. If it was $$$1$$$, it becomes $$$0$$$. This action costs $$$m$$$ energy. (If $$$p+k \gt = n$$$, this action is illegal.)
The total energy spent on all actions (including both moves and toggles) must not exceed $$$E$$$.
Your task is to determine the maximum possible number of ones in the array after performing any sequence of actions within the energy limit.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2000$$$) — the number of test cases.
Each test case consists of:
- a line containing four integers $$$n$$$, $$$k$$$, $$$E$$$, and $$$m$$$ $$$(1 \le n \le 500,\ 1 \le k \lt n,\ 0 \le E \le 10^{18},\ 0 \le m \le 10^{18})$$$;
- a line containing a binary string $$$s$$$ of length $$$n$$$.
It is guaranteed that $$$\left\lfloor \frac{n}{k} \right\rfloor \le 50$$$.
The sum of $$$n$$$ over all test cases will not exceed $$$1000$$$.
For each test case, output a single integer — the maximum possible number of ones in the string after operations with total energy at most $$$E$$$.
35 2 3 1000006 3 2 00000005 2 2 110101
465
65 1 10 2010105 2 10 3000005 2 3 5111116 2 100 00101012 1 100 5008 3 7 210100101
445528
For the first test case, one optimal sequence is: toggle at $$$p=0$$$ (cost $$$1$$$), move to $$$p=1$$$ (cost $$$1$$$), then toggle at $$$p=1$$$ (cost $$$1$$$). The array changes
For the second test case, $$$m=0$$$, so toggles are free and only movement matters. We can toggle at $$$p=0,1,2$$$ with total movement cost $$$2$$$, which turns all positions into $$$1$$$, so the answer is $$$6$$$.
For the third test case, move to $$$p=1$$$ (cost $$$1$$$) and toggle there (cost $$$1$$$). This flips $$$a_1$$$ and $$$a_3$$$ from $$$0$$$ to $$$1$$$, so
This is the easy version of Alien Attack. The only differences between this and the hard version are the constraints on the value of $$$n$$$ and $$$q$$$.
Westin is in a country with $$$n$$$ cities and $$$n-1$$$ bidirectional roads. The road network forms a tree. Cities are numbered from $$$1$$$ to $$$n$$$.
Each city $$$v$$$ has a power value $$$p_v(t)$$$ that depends on time $$$t$$$. Initially, at time $$$t=0$$$, every city has power $$$0$$$.
During an alien invasion, meteors may crash into some cities. It is guaranteed that each city is targeted by at most one meteor in total.
If a meteor crashes into city $$$x$$$ at time $$$t_0$$$ with initial energy $$$\textit{val}$$$, then for any time $$$t \ge t_0$$$, the power contributed by that meteor at city $$$x$$$ is:
This value can be negative (the meteor keeps losing $$$1$$$ energy per second even after reaching $$$0$$$). Cities that have never been hit by a meteor have power $$$0$$$ at all times.
You are given $$$q$$$ queries of two types:
- Type 1: $$$1\ t\ x\ val$$$ — a meteor crashes into city $$$x$$$ at time $$$t$$$ with initial energy $$$val$$$. It is guaranteed that city $$$x$$$ has not been targeted before.
- Type 2: $$$2\ t\ a\ b$$$ — at time $$$t$$$, Westin's friend travels from city $$$a$$$ to city $$$b$$$.
For each type 2 query, output the total power on the simple path from $$$a$$$ to $$$b$$$ at exactly time $$$t$$$:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$).
Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting a road between cities $$$u$$$ and $$$v$$$.
The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 5000$$$).
Each of the next $$$q$$$ lines describes a query in one of the following forms:
- $$$1, t, x, val$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le x \le n$$$, $$$-10^9 \le \textit{val} \le 10^9$$$),
- $$$2, t, a, b$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le a,b \le n$$$).
If at a time t there are both type 1 and type 2 queries, process the type 1 queries first. It is guaranteed that each city appears in at most one type 1 query.
For each type 2 query, output a single integer — the total power on the path from $$$a$$$ to $$$b$$$ at time $$$t$$$.
31 22 341 1 2 52 2 1 32 4 1 32 4 2 2
4 2 2
Initially, all cities have power $$$0$$$.
Query 1: $$$1\ 1\ 2\ 5$$$
A meteor hits city $$$2$$$ at time $$$t_0=1$$$ with initial energy $$$5$$$. So for $$$t \ge 1$$$,
Query 2: $$$2\ 2\ 1\ 3$$$
At time $$$t=2$$$,
Path $$$1 \to 3$$$ is $$$(1,2,3)$$$, so the total is
Query 3: $$$2\ 4\ 1\ 3$$$
At time $$$t=4$$$,
Query 4: $$$2\ 4\ 2\ 2$$$
The path from $$$2$$$ to $$$2$$$ contains only city $$$2$$$, so the answer is
Therefore the outputs are:
You have a mountain range consisting of $$$n$$$ mountains, where the $$$i$$$th mountain has height $$$h_i$$$. To traverse the mountain range, you will buy one pair of sturdy boots and any number of jetpacks. Buying boots with sturdiness $$$s$$$ costs $$$a\cdot s$$$ dollars, while buying $$$k$$$ jetpacks costs $$$b \cdot k$$$ dollars. The boots can be reused and allow you to jump over any mountain $$$i$$$ with height $$$h_i \leq s$$$. Each jetpack can only be used once and allows you to jump over any two adjacent mountains.
Find the minimum cost required to jump over the first $$$i$$$ mountains for each $$$i \in \{1, 2, \ldots, n\}$$$. As long as you clear the first $$$i$$$ mountains, it is ok if using a jetpack also happens to take you past the $$$i+1$$$th mountain.
Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of input test cases.
The first line of each test case contains $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.
The next line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq 10^9$$$) – the cost per unit sturdiness of boots and the cost of a jetpack, respectively.
The next line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_{n}$$$ ($$$1 \leq h_i \leq 10^9$$$) — the heights of the mountains in the mountain range.
It is further guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2\cdot 10^5$$$.
For each test case, output $$$n$$$ integers, the $$$i$$$th of which is the minimum required cost to jump over the first $$$i$$$ mountains of that test case.
152 73 2 7 6 4
6 6 13 13 14
For indices $$$i \in \{1, 2, 3, 4\}$$$, it is optimal to buy boots with sturdiness $$$3$$$, which costs $$$6$$$ dollars. For $$$i \in \{1, 2\}$$$, you don't need to buy any jetpacks, and for $$$i \in \{3, 4\}$$$, you need to buy a single jetpack. For $$$i = 5$$$, it is optimal to buy boots with sturdiness $$$7$$$, and no jetpacks.
You have a rectangular lake with dimensions $$$n$$$ and $$$m$$$. The cell $$$(i, j)$$$ of the lake has a certain depth $$$d_{i, j}$$$. The points $$$(i, j, 0), (i, j, -1), \ldots, (i, j, -d_{i, j}+1)$$$ all contain water, while the points below, such as $$$(i, j, -d_{i, j})$$$ or $$$(i, j, -d_{i, j}-1)$$$ contain rock. The rock below cell $$$(i, j)$$$ has hardness $$$h_{i, j}$$$.
You start at point $$$(a, b, 0)$$$ and want to reach treasure buried at point $$$(u, v, w)$$$. It is guaranteed that $$$(a, b, 0)$$$ contains water, but $$$(u, v, w)$$$ may contain rock.
You can navigate towards the treasure by moving in any of the six cardinal directions (forward/backward, side to side, up/down). You cannot move above the surface of the lake (i.e., to points $$$(x, y, z)$$$ with $$$z \gt 0$$$) or outside the bounds of the lake (i.e., to points $$$(x, y, z)$$$ with $$$x \le 0, x \gt n, y \le 0,$$$ or $$$y \gt m$$$). Moving to point $$$(x, y, z)$$$ takes $$$1$$$ unit of time if $$$(x, y, z)$$$ contains water, and takes $$$h$$$ units of time if $$$(x, y, z)$$$ contains rock with hardness $$$h$$$.
Find the minimum possible time you can take to reach the cell containing the treasure.
Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of input test cases.
The first line of each test case contains $$$n, m$$$ ($$$1 \le n\cdot m \le 10^5$$$) — the dimensions of the lake.
The next line contains $$$a, b, u, v, w$$$ ($$$1 \le a \le n, 1 \le b \le m, 1 \le u \le n, 1 \le v \le m, 0 \le w \le 10^7$$$) — your starting position and the treasure's position.
The next $$$n$$$ lines contain the depths of the lake. The $$$i$$$th line contains $$$m$$$ integers $$$d_{i,1}, d_{i, 2}, \ldots, d_{i, m}$$$ ($$$0 \le d_{i, j} \le 10^7$$$) — the depths of the lake at each position.
The next $$$n$$$ lines contain the hardness of the rock at different parts of the lake. The $$$i$$$th line contains $$$m$$$ integers $$$h_{i,1}, h_{i, 2}, \ldots, h_{i, m}$$$ ($$$2 \le h_{i, j} \le 10$$$) — the hardness of the rock at each position.
It is further guaranteed that the sum of $$$n\cdot m$$$ over all test cases is at most $$$10^5$$$.
For each test case, output a single integer — the minimum time needed for that test case.
35 53 5 3 3 55 3 5 0 31 2 1 0 00 0 0 3 10 2 5 0 00 0 0 3 56 9 6 7 73 3 7 6 29 10 3 3 55 10 8 10 99 8 6 6 105 55 4 3 2 40 5 3 0 03 0 3 0 20 4 4 3 04 0 4 0 40 0 0 2 53 3 2 7 57 8 2 8 88 8 3 10 87 4 9 10 710 9 3 4 65 52 4 1 4 20 0 1 3 41 5 3 3 05 4 0 0 00 4 2 1 40 0 2 0 03 2 6 5 83 8 7 8 96 4 4 3 65 10 8 6 68 7 8 2 9
15173
You have an array of $$$n$$$ positive integers with the $$$i$$$th number being $$$2^{a_i}$$$ for a nonnegative integer $$$a_i$$$. You then perform the following operation $$$n-2$$$ times, leaving $$$2$$$ numbers in the array:
Choose two adjacent numbers in the array $$$a, b$$$, and replace them with their sum ($$$a+b$$$) or their difference ($$$a-b$$$).
Let $$$u, v$$$ be the final numbers remaining in the array. Find the minimum possible value of $$$|u| + |v|$$$.
Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of input test cases.
The first line of each test case contains $$$n$$$ ($$$2 \leq n \leq 5\times 10^5$$$) — the length of the array.
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n}$$$ ($$$0 \leq a_i \leq n$$$) — the exponents of each element.
It is further guaranteed that the sum of $$$n$$$ over all test cases is at most $$$5\times 10^5$$$.
For each test case, output the minimum possible value of $$$|u| + |v|$$$ in binary.
351 3 4 3 053 4 5 5 350 5 1 4 4
111000011
For the first test case, the initial array is $$$s = [2, 8, 16, 8, 1]$$$. We can subtract $$$s[3]$$$ from $$$s[2]$$$ to give $$$s = [2, 8, 8, 1]$$$. We can then subtract $$$s[2]$$$ from $$$s[1]$$$ to give $$$s = [2, 0, 1]$$$. We can then add together the first two numbers to give $$$u = 2, v = 1$$$ and $$$|u| + |v| = 3 = 11_2$$$.
It can be shown that you cannot achieve values smaller than $$$16$$$ and $$$3$$$, respectively, for the other two test cases.
This is the hard version of Alien Attack. The only differences between this and the easy version are the constraints on the value of $$$n$$$ and $$$q$$$.
Westin is in a country with $$$n$$$ cities and $$$n-1$$$ bidirectional roads. The road network forms a tree. Cities are numbered from $$$1$$$ to $$$n$$$.
Each city $$$v$$$ has a power value $$$p_v(t)$$$ that depends on time $$$t$$$. Initially, at time $$$t=0$$$, every city has power $$$0$$$.
During an alien invasion, meteors may crash into some cities. It is guaranteed that each city is targeted by at most one meteor in total.
If a meteor crashes into city $$$x$$$ at time $$$t_0$$$ with initial energy $$$\textit{val}$$$, then for any time $$$t \ge t_0$$$, the power contributed by that meteor at city $$$x$$$ is:
This value can be negative (the meteor keeps losing $$$1$$$ energy per second even after reaching $$$0$$$). Cities that have never been hit by a meteor have power $$$0$$$ at all times.
You are given $$$q$$$ queries of two types:
- Type 1: $$$1\ t\ x\ val$$$ — a meteor crashes into city $$$x$$$ at time $$$t$$$ with initial energy $$$val$$$. It is guaranteed that city $$$x$$$ has not been targeted before.
- Type 2: $$$2\ t\ a\ b$$$ — at time $$$t$$$, Westin's friend travels from city $$$a$$$ to city $$$b$$$.
For each type 2 query, output the total power on the simple path from $$$a$$$ to $$$b$$$ at exactly time $$$t$$$:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).
Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting a road between cities $$$u$$$ and $$$v$$$.
The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$).
Each of the next $$$q$$$ lines describes a query in one of the following forms:
- $$$1, t, x, val$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le x \le n$$$, $$$-10^9 \le \textit{val} \le 10^9$$$),
- $$$2, t, a, b$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le a,b \le n$$$).
If at a time t there are both type 1 and type 2 queries, process the type 1 queries first. It is guaranteed that each city appears in at most one type 1 query.
For each type 2 query, output a single integer — the total power on the path from $$$a$$$ to $$$b$$$ at time $$$t$$$.
31 22 341 1 2 52 2 1 32 4 1 32 4 2 2
4 2 2
Initially, all cities have power $$$0$$$.
Query 1: $$$1\ 1\ 2\ 5$$$
A meteor hits city $$$2$$$ at time $$$t_0=1$$$ with initial energy $$$5$$$. So for $$$t \ge 1$$$,
Query 2: $$$2\ 2\ 1\ 3$$$
At time $$$t=2$$$,
Path $$$1 \to 3$$$ is $$$(1,2,3)$$$, so the total is
Query 3: $$$2\ 4\ 1\ 3$$$
At time $$$t=4$$$,
Query 4: $$$2\ 4\ 2\ 2$$$
The path from $$$2$$$ to $$$2$$$ contains only city $$$2$$$, so the answer is
Therefore the outputs are:
Volcanoes are erupting over the ovine homeland! Help the Sheep King escape the lava.
There are $$$n$$$ islands connected by $$$m$$$ undirected bridges. Each bridge has a length $$$w$$$: crossing that bridge takes exactly $$$w$$$ days (for both the sheep and the lava).
Each island $$$i$$$ has a volcano that erupts on day $$$a_i$$$. When a volcano erupts, all bridges connected to that island burn down and become unusable.
Lava spreads through the bridge network over time, using the same travel times as the Sheep King (it needs $$$w$$$ days to cross a bridge of length $$$w$$$). If lava reaches an island before its volcano erupts, that island burns at the moment lava arrives.
The Sheep King starts on island $$$1$$$ at day $$$0$$$ and wants to reach island $$$n$$$ to escape. If he arrives at an island exactly when it burns, he is considered safe and may still depart from it at that time.
The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.
For each test case:
- The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^5,\ 0 \le m \le 10^5)$$$.
- The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the eruption days of the volcanoes.
- Each of the next $$$m$$$ lines contains three integers $$$x_j$$$, $$$y_j$$$, and $$$w_j$$$ $$$(1 \le x_j \lt y_j \le n, 1 \le w_j \le 10^9)$$$ denoting an undirected bridge between islands $$$x_j$$$ and $$$y_j$$$ of length $$$w_j$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print Yes (case-insensitive) if it is possible to travel from island $$$1$$$ to island $$$n$$$. Otherwise, print No (case-insensitive).
13 2100 2 1001 2 22 3 2
YES
25 746 34 5 60 361 3 231 3 291 5 72 5 254 5 84 5 114 5 295 725 53 5 49 71 2 41 4 71 5 232 5 232 5 243 4 124 5 20
YESNO
The Sheep King can travel from island $$$1$$$ to island $$$2$$$ in $$$2$$$ days. He arrives at island $$$2$$$ on day $$$2$$$, exactly when it burns. He is still safe, so he can continue to island $$$3$$$ and arrive there on day $$$4$$$. The answer is Yes.
The Tiger Little Lu is very interested in biology!
In fact, he owns $$$n$$$ textbooks, with the $$$i$$$th textbook having a textbook topic represented by an integer $$$a_i.$$$ Little Lu enjoys reading certain books more than others. The $$$i$$$th textbook has an enjoyment value of $$$v_i$$$. Note that multiple textbooks can be about the same topic or have the same enjoyment value.
Today, Little Lu is feeling sad as he drinks boba all by himself. To distract himself from this loneliness, the Tiger decides to play a game that his friend Westin taught him.
The game goes as follows: Little Lu will consider all ordered pairs $$$(i,j)$$$, such that $$$L \leq i,j \leq R$$$. Then, for each ordered pair $$$(i,j)$$$:
- Let $$$c_i$$$ be the number of distinct topics that Little Lu has $$$i$$$ textbooks about, and $$$c_j$$$ be the number of topics that he has $$$j$$$ textbooks about.
- If $$$c_i \neq c_j$$$, Lu will add 0 to his score.
- Otherwise, he will choose two indices $$$1 \leq x,y \leq n$$$ , with the highest possible value of $$$v_x \cdot v_y$$$ such that there are exactly $$$i$$$ books with topic $$$a_x$$$ and $$$j$$$ books with topic $$$a_y$$$, and add $$$v_x \cdot v_y$$$ to his score. (If he cannot select such $$$x$$$ and $$$y$$$ to satisfy the constraints, then $$$0$$$ will be added to the score instead.)
Unfortunately, he has forgotten what $$$L$$$ and $$$R$$$ were, so Little Lu will ask you $$$q$$$ questions, each with $$$l_i$$$, and $$$r_i$$$, asking to find the score he will achieve if he plays the game with the given $$$L = l_i$$$ and $$$R = r_i.$$$
He doesn't want to spend all day doing this, so help Lu the Little Tiger solve this problem!
The first line contains two integers, $$$n$$$ and $$$q (1\leq n \leq 5\cdot 10^5, 1\leq q \leq 5\cdot 10^5).$$$
The second line contains $$$n$$$ integers, $$$a_1, a_2, ..... a_n, (1 \leq a_i \leq 10^9)$$$.
The third line contains $$$n$$$ integers, $$$v_1, v_2, ...v_n, (1 \leq v_i \leq 100).$$$
The last $$$q$$$ lines contain two integers, $$$l_i$$$ and $$$r_i (1\leq l_i \leq r_i \leq 10^9)$$$, each pair representing a query.
For each query, print an integer representing the score Little Lu can obtain with the given values of $$$L$$$ and $$$R.$$$
12 61 1 2 2 2 3 4 4 6 6 7 710 4 9 4 5 2 6 1 8 7 3 21 21 33 32 31 124 4
104 221 81 181 221 0
Query $$$ \mathbf{1}$$$ : the ordered pairs are $$$$$$(1,1), (1,2), (2,1), (2,2).$$$$$$
$$$\mathbf{(1,1)}$$$: Lu can only choose $$$x = 6$$$ and $$$y = 6$$$, because the only textbook such that there is exactly $$$1$$$ book with its topic is textbook $$$6$$$, so $$$v_6 \cdot v_6=4$$$.
$$$\mathbf{(1,2)}$$$: there are $$$4$$$ topics that have exactly $$$2$$$ books about each topic, which are topics $$$1,4,6,7$$$. However, there is $$$1$$$ topic with exactly $$$1$$$ book about that topic, which is topic $$$3$$$. Thus, $$$0$$$ will be added to the score.
$$$\mathbf{(2,2)}$$$: we can choose $$$x = 1$$$, because there are exactly $$$i = 2$$$ books with topic $$$a_1$$$, and choose $$$y = 1$$$, because there are exactly $$$j = 2$$$ books with topic $$$a_1.$$$ It can be proven that the greatest product results from these choices for $$$x$$$ and $$$y$$$. $$$v_x \cdot v_y = 100$$$ will be added to the score.
$$$\mathbf{(2,1)}$$$: the number of topics that have $$$2$$$ books about them are different from the number of topics that have $$$1$$$ book about them, so $$$0$$$ is added to the score. Output for Query $$$ \mathbf{1}$$$ is $$$4+0+100+0 = \mathbf{104} .$$$
Additionally, the queries in sample that use the ordered pair $$$\mathbf {(1,3)} $$$ will add $$$\mathbf{18}$$$. The number of topics with exactly $$$3$$$ books about it and the number of topics with exactly $$$1$$$ book about it are both $$$1,$$$ so Lu can choose $$$x = 6$$$ and $$$y = 3,$$$ because there is exactly $$$1=i$$$ book with topic $$$a_6$$$ and $$$3=j$$$ books with topic $$$a_3$$$, and add $$$v_x \cdot v_y = 18$$$ to his score.
On the Ovine Island, you are in charge of a herd of big fat sheeps.
To protect them from big bad wolves, you have arranged them into an $$$n \times m$$$ rectangular pen ($$$n,m \le 2000$$$). Each cell in the pen is either empty (weight $$$0$$$) or contains a sheep with weight $$$g_{i,j},$$$ an integer between $$$[1,10^6]$$$.
Your boss is wondering if there are special properties of the weights of your sheep.
You are given $$$q$$$ queries, each describing a rectangle. For each rectangle, consider all non-empty weights inside it. Determine whether you can choose three different cells in the rectangle such that if their weights are $$$a,b,c$$$, then the largest of them is strictly less than half of their sum: $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$$$$
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2000$$$).
The next $$$n$$$ lines each contain $$$m$$$ integers $$$g_{i,j}$$$ ($$$0 \le g_{i,j} \le 10^6$$$), where $$$g_{i,j}=0$$$ means the cell is empty.
The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$).
Each of the next $$$q$$$ lines contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$), describing a rectangle with corners $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ (inclusive).
For each query, print YES (case-insensitive) if there exist three different non-empty cells inside the rectangle whose weights satisfy $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2},$$$$$$ and print NO (case-insensitive) otherwise.
3 31 0 02 3 100 4 051 1 3 32 1 2 31 1 2 22 1 3 21 1 1 1
YES NO NO YES NO
Query 1: 1 1 3 3
This rectangle covers the entire grid. The non-empty weights inside are: $$$\{1,2,3,10,4\}$$$.
We need three different cells with weights $$$a,b,c$$$ such that $$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$
Choose the triple $$$(2,3,4)$$$. We have $$$\max(2,3,4) = 4$$$ and $$$\frac{2+3+4}{2} = \frac{9}{2} = 4.5$$$.
Since $$$4 \lt 4.5,$$$ the condition holds.
Therefore, the answer for Query 1 is $$$\texttt{YES}$$$.
$$$ $$$
Query 2: 2 1 2 3
This rectangle covers row $$$2$$$ and columns $$$1$$$ through $$$3$$$. The non-empty weights inside are: $$$\{2,3,10\}$$$.
The only possible triple is $$$(2,3,10)$$$. We have $$$\max(2,3,10) = 10$$$ and $$$\frac{2+3+10}{2} = \frac{15}{2} = 7.5$$$.
Since $$$10 \not \lt 7.5$$$, the condition does not hold.
Therefore, the answer for Query 2 is $$$\texttt{NO}$$$.
Westin the sheep is located at the lattice point $$$(x,y)$$$. His private jet can travel to any point inside or on the circle centered at $$$(x,y)$$$ with radius $$$r$$$.
There are two countries. Each country is a parallelogram, and a city is located at every lattice point (integer coordinate) that lies inside the parallelogram. The border of the parallelogram counts as inside.
For each country, Westin can visit the cities whose lattice points lie inside or on his circle. Your task is to compare the number of reachable cities in the two countries.
The vertices of each parallelogram are given in the following order:
- $$$(x_1,y_1)$$$: top-left
- $$$(x_2,y_2)$$$: top-right
- $$$(x_3,y_3)$$$: bottom-left
- $$$(x_4,y_4)$$$: bottom-right
It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis (equivalently, the top and bottom edges are horizontal, so $$$y_1=y_2$$$ and $$$y_3=y_4$$$).
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
Each test case consists of three lines:
- The first line contains three integers $$$x$$$, $$$y$$$, $$$r$$$ ($$$-10^5 \lt x,y \lt 10^5$$$, $$$1 \le r \lt 10^5$$$).
- The second line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$1$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).
- The third line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$2$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).
Borders count as inside. It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis.
Let $$$n$$$ be the vertical span (in lattice rows) of a country: $$$n = y_1 - y_3 + 1$$$ (since $$$(x_1,y_1)$$$ is top-left and $$$(x_3,y_3)$$$ is bottom-left). It is guaranteed that the sum of $$$n$$$ over all countries across all test cases does not exceed $$$10^5$$$.
For each test case, output one integer:
- output $$$1$$$ if Country $$$1$$$ has strictly more reachable cities,
- output $$$2$$$ if Country $$$2$$$ has strictly more reachable cities,
- output $$$3$$$ if both countries have the same number of reachable cities.
10 0 1-1 1 0 1 0 0 1 0-1 0 0 0 0 -1 1 -1
3
For the first sample, the following figure illustrates the two parallelograms; both have the same amount of cities inside the radius of the circle, thus the output is $$$3$$$:
