Республиканская олимпиада по информатике 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 )

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

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

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#include <cstring>
#include <string>
#include <cstdio>
// #include <bits/stdc++.h>

#pragma GCC push_options
#pragma GCC optimize ("O0")

using namespace std;

typedef string str;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;
typedef pair <ld, ld> pld;
typedef ll var;
typedef pair <var, var> pvv;

#define start ios_base::sync_with_stdio(false)
#define updiv(ad, bd) (((ad - 1) / bd ) + 1)
#define mod(ad, bd) ((((ad) % (bd)) + (bd)) % (bd))
#define mxz(ad, bd) ad = max( ad, bd )
#define mnz(ad, bd) ad = min( ad, bd )
#define maxx(ad, bd, c) max(ad, max(bd, c))
#define minn(ad, bd, c) min(ad, min(bd, c))
#define arr(ad, bd, cd) (ad + bd), (ad + bd +cd)
#define all(ad) ad.begin(), ad.end()
#define sortstl(ad) sort(all(ad))
#define sortarr(ad, bd, cd) sort(arr(ad, bd, cd))
#define gl(ad) getline(cin, ad)
#define wfloat(ad) fixed << setprecision(ad)
#define pr(ad, bd) pair <(ad), (bd)>

#define rv reverse
#define nl endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define pu push
#define pp pop
#define in insert
#define er erase
#define sz size
#define mp make_pair
#define np next_permutation
#define lb lower_bound // <=
#define ub upper_bound // <
#define tp top
#define ft front
#define et empty
#define op operator
#define f first
#define s second
#define y1 yyyyy
#define cont continue
// #define x first
// #define y second

pii dr[8] = { mp(2, 1), mp(2, -1), mp(-2, 1), mp(-2, -1), mp(1, 2), mp(1, -2), mp(-1, 2), mp(-1, -2) };

// freopen("text.in", "r", stdin);
// freopen("text.out", "w", stdout);

const int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

const ll B = 31 ; //hashbase
const double EPS = 1e-9 ; //epsilon
const double PI = 3.14159;
const ll LINF = 1e18; //infinity
const ll N = 1e6 + 9; //maxn
const ll M = 1e9 + 7; //mod
const ll INF = 1e18; //infinity

ll n, q;
ll t[4*N];

void update(ll i, ll x, ll v = 1, ll tl = 1, ll tr = n) {
	if (tl == tr && i == tl) {
		t[v] = x;
	}else {
		ll tm = (tl + tr) / 2;
        if (i <= tm) {
            update(i, x, v*2, tl, tm);
        } else {
            update(i, x, v*2+1, tm+1, tr);
        }
		t[v] = t[v*2] + t[v*2+1];
	}
}

ll get(ll l, ll r , ll v = 1, ll tl = 1, ll tr = n) {
	if (l > r)
		return 0;
	if (tl == l && tr == r)
		return t[v];
	ll tm = (tl + tr)/2;
	return get(l, min(tm,r), v*2, tl, tm) + get(max(l, tm+1), r, v*2+1, tm+1, tr);
}

int main() {
    start;
    // freopen("rvq.in", "r", stdin);
    // freopen("rvq.out", "w", stdout);
    int cnt = 0;
    n = N-10;
    cin >> q;
    while (q--) {
        ll t, x;
        cin >> t >> x;
        if (t == 1) {
            update(++cnt, x);
        } else {
            cout << get(1, x-1) << '\n';
            update(x, 0);
        }
    }
}