Cod sursa(job #567042)
#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[4*DN];
ofstream g("nums.out");
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();
}
};
void update(int vn,int ls, int ld) {
if(ls==ld) {
ins[vn]=1;
return;
}
int fs=vn<<1,m=(ls+ld)>>1;
if(pz<=m) update(fs,ls,m);
else update(fs+1,m+1,ld);
ins[vn]=ins[fs]+ins[fs+1];
}
void query(int vn, int ls, int ld) {
if(ls==ld) {
g<<p[ls]<<'\n';
return;
}
int fs=vn<<1,m=(ls+ld)>>1;
if(pz<=ins[fs]) query(fs,1,m);
else {
pz-=ins[fs];
query(fs+1,m+1,ld);
}
}
int main()
{
ifstream f("nums.in");
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]!=v[i-1]) 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;
++i1;
update(1,1,szp);
}else {
pz=vo[i2];
++i2;
//query(1,1,szp);
}
return 0;
}