# Cod sursa(job #2654024)

Utilizator Data 29 septembrie 2020 18:15:40 Nums 0 cpp-64 done Arhiva de probleme 1.35 kb
``````#include <bits/stdc++.h>
#define pii pair<string, int>

using namespace std;

ifstream fin ("nums.in");
ofstream fout ("nums.out");

int n, m,k, aib[100002];
string v[100002];
pii s[100002];
int q[100002], viz[100002], nr[100002], p[100002];

void update (int x) {
for (int i = x; i <= m; i += (i & -i))
aib[i]++;
}

bool cmp (pii a, pii b) {
if (a.first.size() != b.first.size())
return a.first.size() < b.first.size();
else
return a.first < b.first;
}

int main()
{
fin >> n;
m = 0;
for (int i = 1; i <= n; i++) {
int t;
fin >> t;
q[i] = t;
if (t) {
fin >> v[i];
s[++m].first = {v[i], i};
}
else {
fin >> nr[i];
fin.get();
}
}
sort(s + 1,s + m + 1, cmp);
int m1 = 0;
for (int i = 1; i <= m; i++) {
if (i == 1 || s[i].first != s[i - 1].first) {
s[++m1] = s[i];
}
p[s[i].second] = m1;
}
m = m1;
for (int i = 1; i <= n; i++) {
if (q[i]) {
int poz = p[i];
if (!viz[poz])
update(poz);
viz[poz] = 1;
}
else {
int sum = 0, sol = 0;
int j;
for (j = (1 << 16); j; j >>= 1)
if (sol + j < m && sum + aib[sol + j] < nr[i]) {
sol += j;
sum += aib[sol];
}
fout << s[sol + 1].first << "\n";
}
}
return 0;
}
``````