Республиканская олимпиада по информатике 2009 год

Задача B. Фокус

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

2 секунды

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

256 мегабайт

Помните про фокус с мухами, который изобрел Баха? Жома решил посоревноваться с ним и придумал свой фокус! У Жомы есть ящик. Он может запускать туда муху или выпускать. Также, он как хороший дрессировщик знает возраст каждой мухи в минутах с момента ее рождения. А фокус заключается вот в чем: в любой момент он может назвать возраст $K$-й по старшинству мухи, которая находится в ящике среди мух с возрастом от $A$ до $B$ включительно. Попробуйте и вы сделать этот фокус!

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

Первая строка входного файла содержит число $N$ — общее количество событий ($1 \le N \le 2 \cdot 10^5$). Далее следует $N$ строк, каждая из которых описывает одно из событий:

• $+ X$ — в ящик впустили муху с возрастом $X$;
• $- X$ — из ящика выпустили муху с возрастом $X$;
• $? K A B$ — у фокусника спросили возраст $K$-й по старшинству мухи в ящике среди мух с возрастом от $A$ до $B$ включительно ($1 \le K \le 10^5$, $A \le B$);

Возраст мухи ($X$, $A$, $B$) — целое число от $1$ до $10^9$.

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

Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $A$ до $B$ в ящике меньше $K$, то нужно вывести $0$.

Пример:

Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Ответ

2
3
0

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

показать/скрыть код

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define mp(x, y) make_pair(x, y)
#define F first
#define S second
using namespace std;
int q;
unordered_map<int, int> t;
void upd(int x, int y) {
  for (; x <= 1000000000; x += (x & -x)) t[x] += y;
}
int get(int x) {
  int y = 0;
  for (; x > 0; x -= (x & -x)) y += t[x];
  return y;
}
int find(int s) {
  int k = 0;
  for (int l = 29; l >= 0; l--) {
    if (k + (1 << l) <= 1000000000 && t[k + (1 << l)] < s) {
      k += (1 << l);
      s -= t[k];
    }
  }
  return k + 1;
}
int main() {
  speed;
  oprecision;
  // code
  t.reserve(1 << 16);
  t.max_load_factor(0.2);
  cin >> q;
  while (q--) {
    char type;
    int a, b, c;
    cin >> type >> a;
    if (type == '+') {
      upd(a, 1);
    }
    if (type == '-') {
      upd(a, -1);
    }
    if (type == '?') {
      cin >> b >> c;
      int d = find(get(b - 1) + a);
      cout << (d > c ? 0 : d) << "\n";
    }
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

C++

Copy