Республиканская олимпиада по информатике 2017 год, Павлодар


Есеп A. Кезек

Ограничение по времени:
1 second
Ограничение по памяти:
64 megabytes

Бекжан қызықты кезек туралы естіді. Бұл кезекте ықылассыз кассир жұмыс істейді. Бұл кассир онымен ұрсысқанда ғана-ақ клиентке қызмет етеді екен. Кейде кезектегі адамдар маңызды кездесуге кешіккендерін түсініп, кезекке қарамай кассирге өтіп, онымен ұрсысады. Ұрсысқаннан кейін кассир сол клиентке қызмет етіп, оны жібереді. Мысалы, кезексіз өткен адамның аты Ануар болсын. Онда Ануардың алдында кезекте турған әр адам Ануарға өзінің наразылығын белгілі саны бар сөзбен білдіреді. Сөздер саны әр адам үшін белгіленген. Бекжан әр кезексіз өткен адам өзі туралы қанша наразылық сөзін еститінін білгісі келді.
Формат входного файла
Енгізілген мәліметтердің бірінші жолында $N$ бүтін саны — кезектегі әрекеттердің саны берілген ($2 \leq N \leq 5 \cdot 10^5$). Әр әрекеттің сипаттамасы $type$ бүтін санынан басталады ($1 \leq type \leq 2$). Егер $type = 1$ болса, одан кейін $w$ бүтін саны беріледі ($1 \leq w \leq 10^9$). Бұл сұраныс түрі кезекке жаңа адам келгенін білдіреді. Жаңадан келген адамның нөмірі оның алдында нөмір ретінде пайдаланылмаған ең кіші бүтін оң сан болады және ол наразылығын көрсеткендегі сөздер саны $w$ болып саналады. Егер $type = 2$ болса одан кейін $x$ саны беріледі. Бұл сұраныс түрі кезекте тұрған нөмірі $x$ адам кезексіз өткенін білдіреді. Сұраныс кезінде бұл адам кезекте бар екендігіне кепілдік беріледі. Кезектен тым болмаса бір адамның шығатына кепілдік беріледі.
Формат выходного файла
Кезексіз өткен әр адам қанша наразылық сөз санын еститінін шығарыңыз.
Система оценки
  1. $N \le 20$, $w \le 1000$. Топ бөлігінің бағасы: $10$ ұпай.
  2. $N \le 10000$. Топ бөлігінің бағасы: $40$ ұпай.
  3. $N \le 500000$. Топ бөлігінің бағасы: $50$ ұпай.
Пример:
Вход
2
1 1
2 1
Ответ
0
Вход
8
1 8
1 1
1 9
2 2
1 2
1 4
2 5
1 3
Ответ
8
19
Замечание
Бірінші мысалда кезекке бір адам келіп, кассирмен ұрcысып, ешкімнен наразылық сөзін естіген жоқ. Екінші мысалда кезекке басында $8$, $1$ және $9$ наразылық сөздерін айтатын адамдар келеді. Олардың нөмір сандары тиісінше $1$, $2$ және $3$ болады. Одан кейін нөмірі $2$-ші адам кезексіз өтіп, нөмірі $1$-ші адамның наразылық сөздерін естиді ($8$ сөз). Бұл адамнан кейін кезекке наразылық сөз саны $2$ және $4$ адамдар келіп, $4$-ші және $5$-ші нөмірлерді тиісінше алады. Олардан кейін нөмірі $5$-ші адам кезексіз өтіп, нөмірлері $1$-ші, $3$-ші және $4$-ші адамдардан наразылық сөз естиді ($19$ сөз). Ең аяғында кезекке нөмірі $6$-шы және сөз саны $3$ адам қосылады. ( Bekzhan Kassenov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2021-02-09 18:33:40.0 #

кодты корсету/жасыру