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

Задача A. Очередь

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Бекжану рассказали об одной интересной очереди. Это очередь в кассу, в которой работает не особо добросовестный кассир. Кассир в этой очереди обслуживает клиента, только когда клиент ругается с ним. Время от времени кто-то из очереди осознает, что он опаздывает на очень важную встречу, проходит вне очереди, ругается с кассиром, после чего кассир его обслуживает. Допустим, что человека, прошедшего вне очереди зовут Ануар. Каждый человек, стоявший перед Ануаром в очереди, выразит свое недовольство его поступком в виде какого-то количества слов (фиксированного для каждого говорящего). Наблюдавшему за очередью Бекжану стало интересно, сколько же нелестных слов в свой адрес услышит каждый, прошедший вне очереди?

Формат входного файла

Первая строка входных данных содержит целое число $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

Замечание

В первом примере человек пришел в очередь, поругался с кассиром и не выслушивал слов ни от кого. Во втором примере в очередь сначала придут люди, которые скажут $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);
        }
    }
}

C++

Copy