Cod sursa(job #567042)

Utilizator S7012MYPetru Trimbitas S7012MY Data 29 martie 2011 17:40:05
Problema Nums Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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[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;
}