Cod sursa(job #1773309)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 7 octombrie 2016 18:48:10
Problema Schi Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <stdlib.h>
int v[30001],aint1[70001],aint2[70001],f[30001],val;
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
int min(int a,int b)
{
    if(a<b) return a;
    return b;
}
void update(int pos,int st,int dr,int i)
{
    if(st<=i && i<=dr){
        if(st<dr)
        {
            update(pos*2,st,(st+dr)/2,i);
            update(pos*2+1,(st+dr)/2+1,dr,i);
        }
        aint1[pos]=min(aint1[pos],v[i]);
        aint2[pos]=max(aint2[pos],v[i]);
    }
}
void adun(int pos,int st,int dr)
{
    if(aint2[pos]<=val)
        val+=(dr-st+1);
    else
        if(aint1[pos]>val) ;
        else
        {
            adun(pos*2,st,(st+dr)/2);
            adun(pos*2+1,(st+dr)/2+1,dr);
        }
}
void verif(int pos,int st,int dr,int a,int b)
{
    if(a<=st && b>=dr)
        adun(pos,st,dr);
    else
    {
        if(b<st || a>dr) ;
        else
        {
            if(a<=(st+dr)/2) verif(pos*2,st,(st+dr)/2,a,b);
            if(b>(st+dr)/2)  verif(pos*2+1,(st+dr)/2+1,dr,a,b);
        }
    }
}
int main()
{
    int n,i;
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d",&v[i]);
    for(i=1; i<=70000; i++)
        aint1[i]=100000;
    update(1,1,n,n);
    f[n]=v[n];
    for(i=n-1; i>=1; i--)
    {
        val=v[i];
        verif(1,1,n,i+1,n);
        update(1,1,n,i);
        f[i]=val;
    }
    for(i=1; i<=n; i++)
        v[f[i]]=i;
    for(i=1; i<=n; i++)
        printf("%d\n",v[i]);

    return 0;
}