Cod sursa(job #169652)

Utilizator cretuMusina Rares cretu Data 1 aprilie 2008 20:42:08
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#define m ((st+dr)>>1)
#define ns (nod<<1)
#define nd (ns+1)
#define MAX (1<<15)
#define INF 99999
#define mini(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

int s[MAX], val[MAX], p[MAX<<1];
int n, poz, concurent, a, b;

void Build(int nod, int st, int dr)
{
     if (st == dr) 
     {
         p[nod] = st;
         return;       
     }     
     
     p[nod] = st;
     Build(ns, st,  m);
     Build(nd, m+1, dr);
}

int Query(int nod, int st, int dr)
{
    if (a <= st && dr <= b) { return p[nod]; }
    
    int x = INF, y = INF;
    if (a <= m) x = Query(ns, st,  m);
    if (m < b)  y = Query(nd, m+1, dr);
    
    return mini(x, y);
}

void Update(int nod, int st, int dr)
{
     if (st == dr)
     {
         p[nod] = INF;
         s[st] = concurent;
         return;       
     }    
     
     if (poz <= m) Update(ns, st,  m);
     else          Update(nd, m+1, dr);
     
     p[nod] = mini(p[ns], p[nd]); 
}

int main()
{
    int i, j, ok;
    ifstream fin("schi.in");
    fin >> n;
    for (i = 1; i <= n; i++)   
    { 
        fin >> val[i];
        s[i] = 0;
    }
    fin.close();
    
    Build(1, 1, n);
    
    for (i = n; i >= 1; i--)
    {
        a = val[i], b = n;
        for (j = n; j > i; j--)
            if (val[j] <= val[i]) a++;
        poz = Query(1, 1, n);
        concurent = i;
        Update(1, 1, n);        
    }
    
    ofstream fout("schi.out");
    for (i = 1; i <= n; i++)
        fout << s[i] << "\n";
    fout.close();
    
    return 0;
}