Altair Ashurov


Задача №1. 

Задача C. Суммарная площадь

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Альтаиру часто дарят интересные подарки. На этот раз Ариф подарил множество различных точек на плоскости, он конечно поблагодарил Арифа. Но он совсем не знает что делать с этими точками, поэтому он придумал задачу. Альтаир определил функцию $f(S)$, которая считает площадь минимального прямоугольника со сторонами параллельными осям координат, который покрывает все точки из множества $S$ (точка покрыта прямоугольником, когда находится внутри него или на его границе). Но подсчет такой функции кажется ему чем-то слишком простым и скучным, поэтому он хочет посчитать сумму значений функции $f$ по всем возможным непустым подмножествам точек. Так как Альтаир не умеет использовать большие числа, а ответ может быть уж слишком большим, поэтому нужно посчитать его остаток при делении на $10^9 + 7$.
Формат входного файла
В первой строке дано одно натуральное число $n$ ($1 <= n <= 10^5$) — количество точек в подарке. Далее следуют $n$ строк, в $i$-й записана пара чисел $x_i$, $y_i$ ($1 <= x_i, y_i <= 10^9$) — координаты $i$-й точки.
Формат выходного файла
Выведите одно число - ответ на задачу по модулю $10^9 + 7$.
Пример:
Вход 
3
4 10
5 7
7 9
Ответ
19
Замечание
Рассмотрим пример. В этом примере есть 7 непустых подмножеств. Площадь прямоугольника для подножества из первой и второй точки: $f(\{1, 2\}) = 3$. $f(\{1\}) = f(\{2\}) = f(\{3\}) = 0$ $f(\{1, 2\}) = 3$ $f(\{1, 3\}) = 3$ $f(\{2, 3\}) = 4$ $f(\{1, 2, 3\}) = 9$ Сумма по всем $f(S)$ -- $19$. ( Altair Ashurov )
комментарий/решение(1) олимпиада
Задача №2. 

Задача A. Колючие ежи

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

На целочисленной прямой расположено $n$ ежей, каждый еж имеет свою координату - $x_i$ и может передвигаться по прямой как он пожелает. Но к сожалению ежам нельзя далеко уходить, поэтому при передвижении их координата должна быть целым числом между $1$ и $n$. Более того у каждого ежа есть своя скорость передвижения, а именно ежу под $i$-м номером требуется $t_i$ секунд для перехода на соседнюю точку. Ежи очень колючие существа, поэтому еж не доволен когда в одной точке с ним находится другой еж. Какое минимальное время потребуется ежам, чтобы они все стали довольными.
Формат входного файла
В первой строке дано одно натуральное число $n$ ($1 <= n <= 10^5$) — количество ежей. Далее следуют $n$ строк, в $i$ строке дано два числа $x_i$ ($1 <= x_i <= n$) и $t_i$ ($0 <= t_i <= 10^9$) — местоположение $i$-го ежа и время требуемое для передвижения на соседнюю точку $i$-го ежа.
Формат выходного файла
Выведите одно число — минимальное время для того чтобы все ежи стали довольными.
Примеры:
Вход 
3
2 1
2 2
2 3
Ответ
2
Вход 
6
4 1
4 7
1 9
3 0
5 11
2 14
Ответ
1
Замечание
В первом примере первый еж пойдет в точку с номером $1$(на это уйдет $1$ секунда), второй пойдет в точку с номером $3$(на это уйдет $2$ секунды), а третий остается в точке с номером $2$. Во втором примере, первый еж идет в точку номер $3$(на это уйдет $1$ секунда), четвертый еж идет в точку номер $6$($0$ секунд), а остальные ежи остаются на месте. ( Altair Ashurov )
комментарий/решение(1) олимпиада
Задача №3. 

Задача F. Заполнение таблицы

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Таблица размера $2 \times n$ называется красивой если числа в ней возрастают как по строкам, так и по столбцам, более того, все числа в таблице должны образовывать перестановку чисел от $1$ до $2 \cdot n$. Вам дана таблица в которой некоторые клетки заняты, а некоторые свободны. Вы уже умеете заполнять таблицу так, чтобы она стала красивой, и эта задача вам кажется скучной. Поэтому вы хотите узнать сколько есть способов заполнить таблицу таким образом, чтобы она была красивой. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.
Формат входного файла
В первой строке дано одно натуральное число $n$ ($1 <= n <= 2 \cdot 10^5$) — количество столбцов в таблице. Далее следуют $2$ строки, в этих двух строках вам дана сама таблица. Числа в таблице имеют значения от $0$ до $2 \cdot n$, при этом числа от $1$ до $2 \cdot n$ встречаются не более одного раза. Если значение элемента равно $0$, то это клетка считается пустой.
Формат выходного файла
Выведите одно число — ответ на задачу по модулю $10^9 + 7$.
Примеры:
Вход 
3
5 0 6
4 0 0
Ответ
0
Вход 
3
0 2 0
3 0 0
Ответ
2
Замечание
В первом примере нет ни единого способа заполнить таблицу так чтобы она была красивой. Во втором примере есть две красивые таблицы которые могут получиться:

( Altair Ashurov )
комментарий/решение олимпиада