Cod sursa(job #3280040)

Utilizator happyplaneDragos Miu-Baldu happyplane Data 25 februarie 2025 11:34:41
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

const int kMaxN=30005;
int inter[kMaxN],final[kMaxN];
int fen_tree[kMaxN];
int nr_part;

void Update(int val,int poz)
{
    while(poz<=kMaxN)
    {
        fen_tree[poz]+=val;
        poz+=poz&-poz;
    }
}

int Query(int poz)
{
    int sum=0;
    while(poz>0)
    {
        sum+=fen_tree[poz];
        poz-=poz&-poz;
    }
    return sum;
}

int BinSearch(int val)
{
    int left=1,right=nr_part,mij,poz;
    while(left<=right)
    {
        int mid=(left+right)/2;
        mij=Query(mid);
        if(mij==val)
        {
            right=mid-1;
            poz=mid;
        }
        else if(mij<val)
            left=mid+1;
        else
            right=mid-1;
    }
    return poz;
}

int main()
{
    fin>>nr_part;
    for(int i=1;i<=nr_part;++i)
    {
        fin>>inter[i];
        Update(1,i);
    }
    for(int i=nr_part;i>0;--i)
    {
        int poz=BinSearch(inter[i]);
        final[poz]=i;
        Update(-1,poz);
    }
    for(int i=1;i<=nr_part;++i)
        fout<<final[i]<<"\n";
    return 0;
}