Cod sursa(job #2756599)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 1 iunie 2021 19:11:39
Problema Schi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <iostream>
#include <fstream>

#define NMAX 30000

using namespace std;

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

int A, B;
int pozSterg;
int tree[4 * NMAX + 1];
int v[NMAX + 1];
int rez[NMAX + 1];

void creareArbore(int node, int left, int right){
    tree[node] = right - left + 1;

    if(left == right){
        return;
    }

    int mid = left + (right - left) / 2;
    creareArbore(node * 2, left, mid);
    creareArbore(node * 2 + 1, mid + 1, right);
}

int query(int node, int left, int right){
    if(left == right){
        return tree[node];
    }

    int mid = left + (right - left) / 2;
    int rez1 = 0, rez2 = 0;
    if(A <= mid){
        rez1 = query(node * 2, left, mid);
    }
    if(B >= mid + 1){
        rez2 = query(node * 2 + 1, mid + 1, right);
    }

    return rez1 + rez2;
}

void sterg(int node, int left, int right){
    if(left == right){
        tree[node] = 0;
        return;
    }

    int mid = left + (right - left) / 2;

    if(pozSterg <= mid){
        sterg(node * 2, left, mid);
    }
    else {
        sterg(node * 2 + 1, mid + 1, right);
    }

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int main()
{
    int N;
    fin >> N;

    for(int i = 1; i <= N; i++){
        fin >> v[i];
    }

    creareArbore(1, 1, N);

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

        int lo = 0;
        int hi = N + 1;

        while(hi - lo > 1){
            int mid = lo + (hi - lo) / 2;

            A = 1;
            B = mid; //[A, B] imi da intervalul pe care vreau suma
            if(query(1, 1, N) >= v[i]){
                hi = mid;
            }
            else{
                lo = mid;
            }
        }

        //raspunsul se afla in hi
        rez[ hi ] = i;

        pozSterg = hi;
        sterg(1, 1, N); //sterg hi
    }

    for(int i = 1; i <= N; i++){
        fout << rez[i] << "\n";
    }

    return 0;
}