Cod sursa(job #1060224)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 17 decembrie 2013 19:14:28
Problema Schi Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
 int n,a[100005],v[30005],sol[30005],res,qres=0;

 void Update(int nod,int st,int dr,int pos)
 { int m;
   if (st==dr) a[nod]++;
    else
    { m=(st+dr)/2;
      if (pos<=m) Update(2*nod,st,m,pos);
       else Update(2*nod+1,m+1,dr,pos);
       a[nod]=a[2*nod]+a[2*nod+1];
    }
 }

 void Query(int nod,int st,int dr,int x,int y)
 { int m;
    if (x<=st && dr<=y) qres+=a[nod];
      else
      { m=(st+dr)/2;
         if (x<=m) Query(2*nod,st,m,x,y);
         if (y>m) Query(2*nod+1,m+1,dr,x,y);
      }
 }

 int Bsearch(int k)
 { int i,st=1,dr=n,m;
    while(st<dr)
    { m=(st+dr)/2;
       qres=0;
      Query(1,1,n,1,m);
       qres=m-qres;
      if (qres>=k) dr=m-1; else st=m+1;
    }
     m=(st+dr)/2;
         qres=0;
      Query(1,1,n,1,m);
       qres=m-qres;
    if (qres!=k) m++;
   //cout<<m<<"\n";
   return m;
 }
int main()
{ int i;
   f>>n;
  for(i=1;i<=n;i++)
   f>>v[i];

  for(i=n;i>=1;i--)
  { res=Bsearch(v[i]);
      sol[res]=i;
     Update(1,1,n,res);
  }
   for(i=1;i<=n;i++)
    g<<sol[i]<<"\n";
    return 0;
}