Cod sursa(job #2862947)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 6 martie 2022 09:27:25
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

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

int n;
int arbint[100000];
int v[30005];
int ans[30005];

int LfSon(int node)
{
    return node * 2;
}
int RgSon(int node)
{
    return node * 2 + 1;
}

int Query(int node, int lf, int rg, int val)
{
    if (lf == rg)
    {
        return lf;
    }

    int mid = (lf + rg) / 2;
    if (arbint[LfSon(node)] < val)
    {
        return Query(RgSon(node), mid + 1, rg, val - arbint[LfSon(node)]);
    }
    else
    {
        return Query(LfSon(node), lf, mid, val);
    }
}

void Update(int node, int lf, int rg, int pos, int val)
{
    if (lf == rg)
    {
        arbint[node] = val;
        return;
    }

    int mid = (lf + rg) / 2;
    if (pos <= mid)
    {
        Update(LfSon(node), lf, mid, pos, val);
    }
    else
    {
        Update(RgSon(node), mid + 1, rg, pos, val);
    }

    arbint[node] = arbint[LfSon(node)] + arbint[RgSon(node)];
}

void Init(int node, int lf, int rg, int val)
{
    if (lf == rg)
    {
        arbint[node] = val;
        return;
    }

    int mid = (lf + rg) / 2;
    Init(LfSon(node), lf, mid, val);
    Init(RgSon(node), mid + 1, rg, val);

    arbint[node] = arbint[LfSon(node)] + arbint[RgSon(node)];
}


int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    int log = log2(n);
    if ((1 << log) < n)
    {
        log++;
    }

    int upperBound = 1 << log;
    Init(1, 1, upperBound, 1);

    for (int i = n; i > 0; i--)
    {
        int index = Query(1, 1, upperBound, v[i]);
        cout << index << ' ';
        Update(1, 1, upperBound, index, 0);
        ans[index] = i;
    }

    for (int i = 1; i <= n; i++)
    {
        fout << ans[i] << '\n';
    }
}