Cod sursa(job #829381)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 5 decembrie 2012 11:25:19
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#define LS (current_position<<1)
#define RS (current_position<<1)+1
#define  INF (1<<20)
#define NMAX 61002
using namespace std;

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

int N,begin,end,value;
int C[30002];

struct my_struct{int add,nr;}V[NMAX];

void Update(int current_position,int start,int final)
{
    if(start>=begin && final <=end)
        V[current_position].add +=value;
    else
    {
        int med = (start + final) / 2;
        if(begin<=med)
            Update(LS,start,med);
        if(med+1<=end)
            Update(RS,med+1,final);

        if(C[V[LS].nr]+V[LS].add<C[V[RS].nr]+V[RS].add)
             V[current_position].nr = V[LS].nr,V[current_position].add+=V[LS].add;
        else V[current_position].nr = V[RS].nr,V[current_position].add+=V[RS].add;
    }
}

void Refresh(int current_position,int start,int final)
{
    if(start == final);
    else
    {
        int med = (start + final) / 2;
        Refresh(LS,start,med);
        Refresh(RS,med+1,final);
        if(C[V[LS].nr]+V[LS].add<C[V[RS].nr]+V[RS].add)
             V[current_position].nr = V[LS].nr,V[current_position].add+=V[LS].add;
        else V[current_position].nr = V[RS].nr,V[current_position].add+=V[RS].add;
    }
}

int main()
{
    int i,x;
    in>>N;
    for(i=1;i<=N;i++)
        in>>C[i],V[N+i-1].nr = i;
    Refresh(1,1,N);
	for(i=0;i<NMAX;i++)
		V[i].nr = INF,V[i].add = INF;
	return 0;
	
    for(i=1;i<=N;i++)
    {
        out<<(x = V[1].nr)<<'\n';
        begin = x,end = x,value = INF;
        Update(1,1,N);
        begin = 1,end = x,value = 1;
        Update(1,1,N);
    }
    return 0;
}