Cod sursa(job #1724303)

Utilizator tudi98Cozma Tudor tudi98 Data 2 iulie 2016 19:50:47
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <fstream>
#include <iostream>
using namespace std;

int N;
int A[30001];
int data[30001*4];
int Sol[30001];
int index[30001*4];


void Build_Tree(int node,int l,int r)
{
    if (l == r)
    {
        index[node] = l;
        data[node] = 0;
        return;
    }
    int mid = (l+r)>>1;
    Build_Tree(node<<1,l,mid);
    Build_Tree(node<<1|1,mid+1,r);

    data[node] = data[node<<1] + data[node<<1|1];
    if (index[node<<1])
        index[node] = index[node<<1];
    else if (index[node<<1|1])
        index[node] = index[node<<1|1];
    else
        index[node] = 0;
}

void Update1(int node,int l,int r,int pos)
{
    if (l == r)
    {
        index[node] = 0;
        return;
    }

    int mid = (l+r)>>1;
    if (pos <= mid)
        Update1(node<<1,l,mid,pos);
    else
        Update1(node<<1|1,mid+1,r,pos);

    data[node] = data[node<<1] + data[node<<1|1];
    if (index[node<<1])
        index[node] = index[node<<1];
    else if (index[node<<1|1])
        index[node] = index[node<<1|1];
    else
        index[node] = 0;
}

void Update(int node,int l,int r,int pos)
{
    if (l == r)
    {
        data[node]++;
        return;
    }

    int mid = (l+r)>>1;
    if (pos <= mid)
        Update(node<<1,l,mid,pos);
    else
        Update(node<<1|1,mid+1,r,pos);

    data[node] = data[node<<1] + data[node<<1|1];
    if (index[node<<1])
        index[node] = index[node<<1];
    else if (index[node<<1|1])
        index[node] = index[node<<1|1];
    else
        index[node] = 0;
}

int QuerySum(int node,int l,int r,int a,int b)
{
    if (r < a || l > b)
        return 0;
    if (l >= a && r <= b)
        return data[node];
    int mid = (l+r)>>1;
    return QuerySum(node<<1,l,mid,a,b) + QuerySum(node<<1|1,mid+1,r,a,b);
}

int QueryUpperBound(int node,int l,int r,int up)
{
    if (r < up)
        return 0;
    if (l >= up)
        return index[node];
    int mid = (l+r)>>1;
    int q1 = QueryUpperBound(node<<1,l,mid,up);
    if (q1)
        return q1;
    return QueryUpperBound(node<<1|1,mid+1,r,up);
}

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

    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> A[i];
    Build_Tree(1,1,N);
    for (int i = N; i >= 1; i--)
    {
        int bef = QuerySum(1,1,N,1,A[i]);
        //cout << bef << "\n";
        int p = QueryUpperBound(1,1,N,A[i]+bef);
        Sol[p] = i;
        //cout << i << " on " << p << "\n";
        Update(1,1,N,A[i]);
        Update1(1,1,N,p);
    }

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