Cod sursa(job #2946321)

Utilizator Laurentiu_BTarabic Laurentiu Gabriel Laurentiu_B Data 24 noiembrie 2022 18:56:42
Problema Schi Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<iostream>
#include<fstream>
using namespace std;

long long int st[200000];

void update(int node,int from,int to,int pos,long long val)
{
  if(to==from)
  {
     st[node]=val;
     return;
  }
  int mid=(from+to)/2;
  if(pos<=mid)
    update(node*2,from,mid,pos,val);
  else
    update(node*2+1,mid+1,to,pos,val);
  st[node]=st[node*2]+st[node*2+1];
}

 long long int query(int node,int from,int to,int qlf,int qrt)
{
   long long int smax=0;
   if(qlf<=from&&qrt>=to)
   {
       return st[node];
   }
   int mid=(from+to)/2;
   if(qlf<=mid)
   {
      long long int s=query(node*2,from,mid,qlf,qrt);
       smax=smax+s;
   }
   if(qrt>=mid+1)
   {
       long long int s=query(node*2+1,mid+1,to,qlf,qrt);
       smax=smax+s;
   }
   return smax;
}

int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");
    long long int n,v[30002],a[30002];
    f>>n;
    for(int i=1;i<=n;i++)
        update(1,1,n,i,1);
    for(int i=1;i<=n;i++)
        f>>v[i];
    for(int i=n;i>=1;i--)
    {
     long long  int st=1,dr=n,mid,poz;
      while(st<=dr)
      {
        mid=(st+dr)/2;

        long long int s=query(1,1,n,1,mid);
        if(s<v[i])
              st=mid+1;
        else
          {dr=mid-1;
        poz=mid;}
      }
      update(1,1,n,poz,0);
       a[poz]=i;
    }
    for(int i=1;i<=n;i++)
        g<<a[i]<<endl;
}