Cod sursa(job #3243085)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 15 septembrie 2024 16:52:41
Problema Schi Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "schi";

std :: ifstream in (FILENAME + ".in");

std :: ofstream out (FILENAME + ".out");

const int NMAX = 3e4 + 5;

int n;

int x;

int y;

int c;

int zeros;

int i;

int v[NMAX];

int arb[4 * NMAX];

int copac[4 * NMAX];

std :: vector <std :: pair <int, int>> ans;

void update_search(int nod, int st, int dr)
{
    if(st == dr)
    {
        copac[nod] = 1;

        ans.push_back(std :: make_pair(st, n - i + 1));
    }
    else
    {
        int mij = (st + dr) / 2;

        if(x > (mij - st + 1) - copac[nod * 2])
        {
            x -= ((mij - st + 1) - copac[nod * 2]);

            update_search(nod * 2 + 1, mij + 1, dr);
        }
        else
        {
            update_search(nod * 2, st, mij);
        }

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

int query(int nod, int st, int dr)
{
    if(x <= st && y >= dr)
    {
        return arb[nod];
    }

    int mij = (st + dr) / 2;

    if(y <= mij)
    {
        return query(nod * 2, st, mij);
    }
    else if(x > mij)
    {
        return query(nod * 2 + 1, mij + 1, dr);
    }

    return query(nod * 2, st, mij) + query(nod * 2 + 1, mij + 1, dr);
}

int query1(int nod, int st, int dr)
{
    if(x <= st && y >= dr)
    {
        return copac[nod];
    }

    int mij = (st + dr) / 2;

    if(y <= mij)
    {
        return query1(nod * 2, st, mij);
    }
    else if(x > mij)
    {
        return query1(nod * 2 + 1, mij + 1, dr);
    }

    return query1(nod * 2, st, mij) + query1(nod * 2 + 1, mij + 1, dr);
}

void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        arb[nod] ++;
    }
    else
    {
        int mij = (st + dr) / 2;

        if(x <= mij)
        {
            update(nod * 2, st, mij);
        }
        else
        {
            update(nod * 2 + 1, mij + 1, dr);
        }

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

int main()
{
    std :: iostream :: sync_with_stdio(false);

    in.tie(NULL);

    out.tie(NULL);

    in >> n;

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

    std :: reverse(v + 1, v + n + 1);

    for(i = 1; i <= n; i ++)
    {
        x = 1;

        y = v[i];

        c = query(1, 1, n);

        x = v[i];

        update(1, 1, n);

        x = 1;

        y = v[i] + c - 1;

        if(y)
        {
            zeros = y - query1(1, 1, n);

            x = zeros + 1;
        }
        else
        {
            x = 1;
        }

        update_search(1, 1, n);

    }

    std :: sort(ans.begin(), ans.end());

    for(auto i : ans)
    {
        out << i.second << '\n';
    }

    x = 1;

    y = n;

    return 0;
}