Cod sursa(job #212150)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 4 octombrie 2008 14:58:44
Problema Schi Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#define lg_max 60001

using namespace std;

ifstream fin("schi.in");
ofstream fout ("schi.out");

int h_min[2*lg_max];
int h_poz[lg_max];
int val,poz;

int maxxx(int a,int b)
{
    return a>b?a:b;
}

void baga(int nod,int st,int dr)
{
    if (st>dr)
        return ;
    if (st==dr)
    {
        h_min[nod]=val;
        h_poz[nod]=poz;
        return ;
    }
    int left=nod<<1;
    int right=left+1;
    int mij=(st+dr)>>1;
    if (poz<=mij)
        baga(left,st,mij);
    else
        baga(right,mij+1,dr);
    //vad care este mai mic si care are cea mia pmare pozitie in ca z de egalitate
    if (h_min[left]<h_min[right])
    {
        h_min[nod]=h_min[left];
        h_poz[nod]=h_poz[left];
    }
    else
        if (h_min[left]>h_min[right])
        {
            h_min[nod]=h_min[right];
            h_poz[nod]=h_poz[right];
        }
        else
        {
            h_min[nod]=h_min[left];
            h_poz[nod]=maxxx(h_poz[left],h_poz[right]);
        }
}

void citire()
{
    int sir[lg_max],n;
    fin>>n;
    for (int i=1;i<=2*n+1;i++)
        h_min[i]=100*lg_max;
    for (int i=1;i<=n;i++)
    {
            fin>>sir[i];
            poz=i;
            val=sir[i];
            baga(1,1,n);
    }
    for (int i=n;i>=1;i--)
    {
        fout<<h_poz[1]<<"\n";
        poz=h_poz[1];
        val=n+1;
        baga(1,1,n);
    }
}

int main ()
{
    citire();
    return 0;
}