Cod sursa(job #1470033)

Utilizator acomAndrei Comaneci acom Data 10 august 2015 11:43:37
Problema Schi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<cstring>
using namespace std;
#define NMAX 30005
#define INF 0x3f3f3f3f
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,x,A[NMAX<<2],B[NMAX<<2],V[NMAX<<2],C[NMAX];
void update0(int nod, int st, int dr, int p, int v)
{
    if (st==dr)
    {
        A[nod]=B[nod]=v;
        V[nod]=0;
        return ;
    }
    int mij=(st+dr)/2;
    V[nod*2]+=V[nod], V[nod*2+1]+=V[nod], V[nod]=0;
    if (p<=mij) update0(nod*2,st,mij,p,v);
    else update0(nod*2+1,mij+1,dr,p,v);
    A[nod]=min(A[nod*2]+V[nod*2],A[nod*2+1]+V[nod*2+1]);
    B[nod]=max(B[nod*2]+V[nod*2],B[nod*2+1]+V[nod*2+1]);
}
void update(int nod, int st, int dr, int p, int v)
{
    if (A[nod]+V[nod]>=INF) return ;
    if (A[nod]+V[nod]>=v)
    {
        ++V[nod];
        return ;
    }
    int mij=(st+dr)/2;
    V[nod*2]+=V[nod], V[nod*2+1]+=V[nod], V[nod]=0;
    if (B[nod*2]+V[nod*2]>=v) update(nod*2,st,mij,p,v);
    if (B[nod*2+1]+V[nod*2+1]>=v) update(nod*2+1,mij+1,dr,p,v);
    A[nod]=min(A[nod*2]+V[nod*2],A[nod*2+1]+V[nod*2+1]);
    B[nod]=max(B[nod*2]+V[nod*2],B[nod*2+1]+V[nod*2+1]);
}
int query(int nod, int st, int dr, int p)
{
    if (st==dr)
        return A[nod]+V[nod];
    int mij=(st+dr)/2;
    V[nod*2]+=V[nod], V[nod*2+1]+=V[nod], V[nod]=0;
    if (p<=mij) return query(nod*2,st,mij,p);
    else return query(nod*2+1,mij+1,dr,p);
}
int main()
{
    int i;
    memset(A,0x3f,sizeof(A));
    fin>>n;
    for (i=1;i<=n;++i)
    {
        fin>>x;
        update(1,1,n,i,x);
        update0(1,1,n,i,x);
    }
    for (i=1;i<=n;++i)
        C[query(1,1,n,i)]=i;
    for (i=1;i<=n;++i)
        fout<<C[i]<<"\n";
    return 0;
}