Cod sursa(job #2783357)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 14 octombrie 2021 12:11:23
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
#define DIM 30000

using namespace std;

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

int aint[4*DIM+5], sol[DIM+5], p[DIM+5];
int n, poz, lst, crt;

void suma(int nod, int st, int dr, int left, int right){
    if(left <= st && dr <= right){
        crt += aint[nod];
        return;
    }

    int md=(st + dr)/2;

    if(left <= md)
        suma(2*nod, st, md, left, right);

    if(right > md)
        suma(2*nod+1, md+1, dr, left, right);

    aint[nod] = aint[2*nod] + aint[2*nod+1];
}

void update(int nod, int st, int dr, int k, int x){
    if(st == dr){
        aint[nod] = 1;
        sol[st]=x;
        return;
    }

    int md=(st + dr)/2;

    if(k <= md)
        update(2*nod, st, md, k, x);

    if(k >  md)
        update(2*nod+1, md+1, dr, k, x);

    aint[nod] = aint[2*nod] + aint[2*nod+1];
}

int main (){
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>p[i];


    for(int i=n; i>=1; i--){

        lst = 0;
        poz = p[i];
        while(true){

            crt=0;
            suma(1, 1, n, 1, poz);

            if(lst != crt){
                poz += (crt-lst);
                lst=crt;
            }else
                break;
        }

        update(1, 1, n, poz, i);
    }

    for(int i=1; i<=n; i++)
        fout<<sol[i]<<"\n";
    return 0;
}
/**         3
        3      0
     3      0     0
 1      2      0     0
1 1    1 1    1 1   1 1
{1}
{1}
{1}
sol: 7 2 8 6 1 3 5 4
{1}
1:1
2:1
3:3
4:4
5:4
6:2
7:1
8:3
**/