Ball momentum#234

Ball momentum (Editorial)

Розберемо умову. Пара $(i, j)$ підходить, якщо її складність не менша за складність будь-якої пари $(i^{'}, j^{'})$ (i', j'), у якої $i^{'} \neq = i$ i' \ne i і $j^{'} \neq = j$ j' \ne j. Максимум по таких парах дорівнює

(i^{'} \neq = i max w_{i^{'}}) \cdot (j^{'} \neq = j max p_{j^{'}}),

\Bigl(\max_{i' \ne i} w_{i'}\Bigr) \cdot \Bigl(\max_{j' \ne j} p_{j'}\Bigr),

бо ваги й потужності додатні й вибираються незалежно.

Позначимо $W$ — максимум масиву $w$ , $W_{2}$ W_2 — другий максимум, $c_{W}$ c_W — скільки разів трапляється $W$ ; аналогічно $P$ , $P_{2}$ P_2, $c_{P}$ c_P для масиву $p$ . Тоді $max_{i^{'} \neq = i} w_{i^{'}}$ \max_{i' \ne i} w_{i'} дорівнює $W_{2}$ W_2, якщо $w_{i} = W$ w_i = W і $c_{W} = 1$ c_W = 1, і $W$ в усіх інших випадках.

Тепер ключове спостереження: якщо $w_{i} < W$ w_i < W і $p_{j} < P$ p_j < P, то права частина дорівнює $W \cdot P$ W \cdot P, що строго більше за $w_{i} p_{j}$ w_i p_j, — пара не підходить. Отже, у будь-якій підхожій парі $w_{i} = W$ w_i = W або $p_{j} = P$ p_j = P. Це дозволяє не перебирати всі $n^{2}$ n^2 пар.

Випадок 1: $w_{i} = W$ w_i = W і $p_{j} = P$ p_j = P. Тоді ліва частина — глобальний максимум добутку, тому нерівність виконується завжди. Таких пар рівно $c_{W} \cdot c_{P}$ c_W \cdot c_P.

Випадок 2: $w_{i} = W$ w_i = W, $p_{j} < P$ p_j < P. Тоді $max_{j^{'} \neq = j} p_{j^{'}} = P$ \max_{j' \ne j} p_{j'} = P. Якщо $c_{W} \geq 2$ c_W \ge 2, умова перетворюється на $W p_{j} \geq W P$ W p_j \ge W P, тобто $p_{j} \geq P$ p_j \ge P — суперечність, підхожих пар немає. Якщо ж $c_{W} = 1$ c_W = 1, умова стає $W \cdot p_{j} \geq W_{2} \cdot P$ W \cdot p_j \ge W_2 \cdot P; лишається порахувати, скільки $p_{j} < P$ p_j < P їй задовольняють.

Випадок 3 симетричний до другого.

Кожен випадок обробляється одним проходом, тому загальна складність — $O (n)$ . Добутки сягають $1 0^{18}$ 10^{18}, тому рахуйте у 64-бітному типі.

(i^{'}, j^{'})

i^{'} \neq = i

j^{'} \neq = j

(i^{'} \neq = i max w_{i^{'}}) \cdot (j^{'} \neq = j max p_{j^{'}}),

W_{2}

c_{W}

P_{2}

c_{P}

max_{i^{'} \neq = i} w_{i^{'}}

W_{2}

w_{i} = W

c_{W} = 1

w_{i} < W

p_{j} < P

W \cdot P

w_{i} p_{j}

w_{i} = W

p_{j} = P

n^{2}

w_{i} = W

p_{j} = P

c_{W} \cdot c_{P}

w_{i} = W

p_{j} < P

max_{j^{'} \neq = j} p_{j^{'}} = P

c_{W} \geq 2

W p_{j} \geq W P

p_{j} \geq P

c_{W} = 1

W \cdot p_{j} \geq W_{2} \cdot P

p_{j} < P

1 0^{18}