Cod sursa(job #3163840)

Utilizator emazareMazare Emanuel emazare Data 1 noiembrie 2023 12:45:21
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>

using namespace std;

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

const int Nmax = 30005;
int n,aib[4*Nmax],aint[4*Nmax];

void update_aib(int x, int y){
    for(int i=x;i<=n;i+=(i&(-i)))
        aib[i]+=y;
}
int query(int x){
    if(x == 0)
        return Nmax;
    int s = 0;
    for(int i=x;i>0;i-=(i&(-i)))
        s+=aib[i];
    return s;
}
bool check(int a, int b){
    if(a == 0)
        return 0;
    if(b == 0)
        return 1;
    int i = query(a), j = query(b);
    if(i<j || (i == j && a>b))
        return 1;
    return 0;
}
void build(int node, int st, int dr){
    if(st == dr){
        aint[node] = st;
        return;
    }
    int mid = (st+dr)/2;
    build(node+node, st, mid);
    build(node+node+1, mid+1, dr);
    if(check(aint[node+node], aint[node+node+1]))
        aint[node] = aint[node+node];
    else
        aint[node] = aint[node+node+1];
}
void update(int node, int st, int dr, int x){
    if(st == dr){
        aint[node] = 0;
        return;
    }
    int mid = (st+dr)/2;
    if(x<=mid)
        update(node+node, st, mid, x);
    else
        update(node+node+1, mid+1, dr, x);
    if(check(aint[node+node], aint[node+node+1]))
        aint[node] = aint[node+node];
    else
        aint[node] = aint[node+node+1];
}

int main()
{
    int p,c,i;
    fin >> n;
    p = 0;
    for(i=1;i<=n;i++){
        fin >> c;
        update_aib(i,c-p);
        p = c;
    }
    build(1,1,n);
    for(i=1;i<=n;i++){
        int x = aint[1];
        fout << x << '\n';
        update(1,1,n,x);
    }
    return 0;
}