Cod sursa(job #3151480)

Utilizator AndyGooShooterDurlea Andrei AndyGooShooter Data 21 septembrie 2023 16:29:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct BinaryIndexedTree{
    // [1-indexed]
    // [uses <vector>, <algorithm>]

    int n;
    vector <int> tree;

    BinaryIndexedTree(int Size) : n(Size) { // Constructor
        tree.resize(n + 1, 0);
    }

    void Update(int i, int val){ // Adds a value to a specified place whitin the BIT
        while(i <= n){
            tree[i] += val;
            i += (i & -i);
        }
    }
    int Query(int i){ // Returns the sum up to specified place
        int sum = 0;
        while(i > 0){
            sum += tree[i];
            i -= (i & -i);            
        }
        return sum;
    }
    int RangeQuery(int i, int j){ // Retruns the sum between two places
        return Query(j) - Query(i - 1);
    }
    int Src(int val){ // Returns the first place where the sum is equal to val
        int sum = 0, pos = 1 << 30, right = 0;

        while(pos != 0){
            if(right + pos <= n && sum + tree[right + pos] < val){
                sum += tree[right + pos];
                right += pos;
            }
            pos >>= 1;
        }        
        return right + 1;
    }
};




int main()
{
    
    int n;
    vector <int> rank, s;
    fin >> n;
    rank.resize(n + 1);
    s.resize(n + 1);
    BinaryIndexedTree BIT(n);

    for(int i = 1; i <= n; i ++) {
        fin >> rank[i];
        BIT.Update(i, 1);
    }

    for(int i = n; i >= 1; i --) {
        int pos = rank[i];

        pos = BIT.Src(pos);

        BIT.Update(pos, -1);
        s[pos] = i;
    }

    for(int i = 1; i <= n; i++)
        fout << s[i] << "\n";
    return 0;
}