Cod sursa(job #567156)

Utilizator S7012MYPetru Trimbitas S7012MY Data 29 martie 2011 19:37:27
Problema Nums Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#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;
}