Altair Ashurov


Есеп №1. 

Есеп C. Жалпы аудан

Ограничение по времени:
2 seconds
Ограничение по памяти:
256 megabytes

Альтаирге жиі қызықты сыйлықтар беріледі. Бұл жолы Ариф оған ұшақта әртүрлі нүктелер жиынын берді, әрине ол Арифке алғыс айтты. Бірақ ол бұл нүктелермен не істеу керектігін мүлде білмейді, сондықтан ол есеп ойлап тапты. Альтаир $S$ жиынындағы барлық нүктелерді қамтитын, жақтары координат осьтеріне параллель, ең кішкентай тіктөртбұрыштың ауданын есептейтін $f(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 seconds
Ограничение по памяти:
256 megabytes

Бүтін сандар түзуінде $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 second
Ограничение по памяти:
256 megabytes

Өлшемі $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 )
комментарий/решение олимпиада