Cod sursa(job #2662054)

Utilizator betybety bety bety Data 23 octombrie 2020 13:23:27
Problema Nums Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("nums.in");
ofstream out("nums.out");
typedef pair<string,int> pisi;
const int lim=1e5+4;
string a[lim];
bool ok[lim];
pisi s[lim];
int nr[lim];
int u[lim];
int cnt;
bool mycmp(pisi a,pisi b)
{
    if(a.first.size()!=b.first.size())
        return a.first.size()<b.first.size();
    return a.first<b.first;
}
int tree[4*lim];
void update(int nod,int l,int r,int poz)
{
    if(l==r)
    {
        tree[nod]=1;
        ok[l]=true;
        return ;
    }
    int med=(l+r)/2;
    if(poz<=med) update(2*nod,l,med,poz);
    else update(2*nod+1,med+1,r,poz);
    tree[nod]=tree[2*nod]+tree[2*nod+1];
}
int query(int nod,int l,int r,int k)
{
    if(l==r) return l;
    int med=(l+r)/2;
    if(tree[2*nod]>=k)
        return query(2*nod,l,med,k);
    return query(2*nod+1,med+1,r,k-tree[2*nod]);
}
int main()
{
    int tst,t;
    in>>tst;
    for(int w=1;w<=tst;++w)
    {
        in>>t;
        if(t==0)
            in>>nr[w];
        else ++cnt,
             in>>s[cnt].first,
             s[cnt].second=w;
    }
    int r=0;
    sort(s+1,s+cnt+1,mycmp);
    a[++r]=s[1].first;
    for(int i=2;i<=cnt;++i)
    if(s[i].first!=s[i-1].first)
        a[++r]=s[i].first,u[s[i].second]=r;
    else u[s[i].second]=r;
    for(int w=1;w<=tst;++w)
    {
        if(nr[w])
            out<<a[query(1,1,r,nr[w])]<<'\n';
        else if(!ok[u[w]])
            update(1,1,r,u[w]);
    }
    return 0;
}