Cod sursa(job #567156)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#define DN 100005
using namespace std;
string v[DN],p[DN],di[DN];
int op[DN],vo[DN],szv,szo,szp,pz,ins[DN],viz[DN];
struct cmp {
bool operator() (const string &a, const string &b) const {
if(a.size() == b.size()) return a.compare(b) < 0;
return a.size() < b.size();
}
};
inline int lsb(int x) {
return (x & -x);
}
void update(int p) {
for(;p<=szp; p+=lsb(p)) ++ins[p];
}
int query(int p) {
int r=0;
for(;p;p-=lsb(p)) r+=ins[p];
return r;
}
int main()
{
ifstream f("nums.in");
ofstream g("nums.out");
int n;
f>>n;
for(int i=1; i<=n; ++i) {
f>>op[i];
if(1==op[i]) {
f>>v[++szv];
di[szv]=v[szv];
}
else f>>vo[++szo];
}
sort(v+1,v+szv+1,cmp());
p[++szp]=v[1];
for(int i=2; i<=szv; ++i) if(v[i]!=p[szp]) p[++szp]=v[i];
int i1,i2;
i1=i2=1;
for(int i=1; i<=n; ++i)
if(1==op[i]) {
pz=lower_bound(p+1,p+szp+1,di[i1],cmp())-p;
if(viz[pz]) continue;
viz[pz]=1;
++i1;
update(pz);
}else {
pz=vo[i2];
++i2;
int step=(1<<17),pf=0;
for(;step;step>>=1) if(pf+step<=szp && query(pf+step)<pz)
pf+=step;
g<<p[pf+1]<<'\n';
}
return 0;
}