Cod sursa(job #2980277)

Utilizator Luca529Taschina Luca Luca529 Data 16 februarie 2023 12:28:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int x[30001], n, y[30001], z[30001];
void Update(int a, int v)
{while(a<=n)
 {y[a]+=v;
  a=a+(a&(-a));
 }
}

int Query(int a)
{int s=0;
 while(a>0)
 {s+=y[a];
  a=a-(a&(-a));
 }
 return s;
}

int CB(int p)
{int st=1, dr=n, mij, poz=n;

  while(st<=dr)
  {mij=(st+dr)/2;
   int v=Query(mij);

   if(v>=p)poz=mij, dr=mij-1;
   else st=mij+1;
  }
  return poz;
}

int main()
{   int a;
    fin>>n;
    for(int i=1;i<=n;i++)
    {fin>>a;
     x[i]=a;
     Update(i, 1);
    }
    for(int i=n;i>0;i--)
    {int p=CB(x[i]);
      Update(p, -1);
      z[p]=i;
    }

    for(int i=1;i<=n;i++)
    fout<<z[i]<<"\n";
    return 0;
}