Cod sursa(job #2443246)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 27 iulie 2019 10:37:37
Problema Farfurii Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>

using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
long long n,k,v[100005],i,d,ai[400005];
void Update(long long  poz, long long  val, long long  nod, long long  a, long long  b)
{
    if(a==b)
    {
        ai[nod]+=val;
        return;
    }
    long long  mij=(a+b)/2;
    if(mij>=poz)
        Update(poz,val,nod*2,a,mij);
    else
        Update(poz,val,nod*2+1,mij+1,b);
    ai[nod]=ai[nod*2]+ai[nod*2+1];
}
long long  query(long long  nod, long long  a, long long  b, long long  qa, long long  qb)
{
    if(a>=qa && qb>=b)
    {
        return ai[nod];
    }
    long long  rez1=0,rez2=0,mij=(a+b)/2;
    if(qa<=mij)
        rez1=query(nod*2,a,mij,qa,qb);
    if(qb>mij)
        rez2=query(nod*2+1,mij+1,b,qa,qb);
    return rez1+rez2;
}
long long cautbin(long long x)
{
    long long st=1, dr=n,mij=0;
    long long s=0, poz=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        s=query(1,1,n,1,mij);
        if(x<=s)
        {
            poz=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return poz;
}
int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++)
        Update(i,1,1,1,n);
    for(i=1;i<=n;i++)
    {
        if((n-i)*(n-i-1)/2>=k)
            d=0;
        else
            d=k-(n-i)*(n-i-1)/2;
        v[i]=cautbin(d+1);
        Update(v[i],-1,1,1,n);
        k-=d;
    }
    for(i=1;i<=n;i++)
        g<<v[i]<<' ';
    return 0;
}