Accepted implementation for the problem 1208D in codeforces

codeforces-1208D.cpp

/*
 * =====================================================================================
 *
 *       Filename:  1208D.cpp
 *
 *    Description:  codeforces 1208D. Restore Permutation
 *
 *        Version:  1.0
 *        Created:  2019年09月05日
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  lionking
 *   Organization:  None
 *
 * =====================================================================================
 */

#include <cstdio>

using namespace std;

typedef long long int lli_t;


// update the value at index 'index' with change 'val' in binary indexed tree
void update(lli_t *bit, int N, int index, lli_t val)
{
    for (; index <= N; index += (index & (-index))) {
        bit[index] += val;
    }
}

// Given val (s[i] in problem description), find the desired p[i]
int query(lli_t *bit, int N, int logN, lli_t val)
{
    int ans = 0;
    for (int i = logN; i >= 0; --i) {
        auto idx = ans + (1 << i);
        if ((idx <= N) && (bit[idx] <= val)) {
            ans = idx;
            val -= bit[idx];
        }
    }

    return (ans + 1);
}

int main()
{
    constexpr int MAXN = 200007;
    // bit: binary indexed tree (BIT)
    lli_t bit[MAXN] = {0}, p[MAXN];
    int N;

    scanf("%d", &N);
    // read s[i] and construct BIT
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", p + i);
        update(bit, N, i, i);
    }

    int logN = 0;
    for (int x = N; x > 0; x >>= 1, ++logN) {}

    // find the answer with the help of BIT from back to front
    for (int i = N; i > 0; --i) {
        const auto ans = query(bit, N, logN, p[i]);
        p[i] = ans;
        update(bit, N, ans, -ans);
    }

    for (int i = 1; i <= N; ++i) {
        printf("%lld ", p[i]);
    }
    putchar('\n');

    return 0;
}