Cod sursa(job #2532271)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 27 ianuarie 2020 17:35:26
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;



vector <int> tree (150001 , 0);
vector <int> players(30001);
vector <int> results(30001);

ifstream fin;
ofstream fout;

const int left_val = 1;
int right_val;

void update (int nod, int left, int right, int position, int value){
    if(left == right){
        tree[nod] = value;
        return;
    }

    int half = (left + right) /2;

    if (position <= half)
        update ((2 *nod) , left, half, position, value);
    else
        update ((2*nod + 1) , half+1 , right, position , value);

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



int query (int nod, int left, int right,int a,int b){
    int to_return = -1;

    if (left == a && right == b)
        return tree[nod];

    int half = (left + right) /2;
    int val1=0, val2=0;

    if (a <= half && b <= half) to_return = query ((2*nod) , left, half, a, b);
    if (a <= half && b > half) {
        val1 = query ((2*nod) , left, half , a, half);
        val2 = query ((2*nod+1), half+1, right, half+1, b);
        to_return = val1 + val2;
    }

    if (a> half && b> half) to_return = query ((2*nod+1), half+1 ,right, a, b);

    return to_return;

}

int n, i;

int main (void){
    int left_side, right_side, to_be_added, query_result, aux, last_aux;
    bool first_time;

    fin.open("schi.in");
    fin>>n;

    for (right_val = 1; right_val<n; right_val<<=1);

    for (i=1; i<=n; i++)
        fin>>players[i];


    for (i=n; i>0; i--){
        left_side = 1;
        last_aux = 0;

        right_side = players[i];
        aux = query (1, left_val, right_val, left_side, right_side);
        right_side += aux;

        for (; aux - last_aux; right_side += (aux-last_aux)) {
            last_aux = aux;
            aux = query (1, left_val, right_val, left_side, right_side);
        }

        aux += players[i];
        results[aux] = i;

        update(1,left_val, right_val, aux, 1);
    }

    fout.open("schi.out");
    for (i=1; i<=n; i++)
        fout<<results[i]<<"\n";

    return 0;
}