Cod sursa(job #2300987)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 12 decembrie 2018 14:52:25
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#define dim 30001
using namespace std;

ifstream f ("schi.in");
ofstream g ("schi.out");

int tree[4 * dim + 13];
int N, M, A[dim], B[dim], pozi, i;
void Update(int nod, int currL, int currR, int pos, int val) {
     if ( currL == currR ) {
          tree[nod] = val;
          return;
     }

     int mid = currL + (currR - currL) / 2;
     if ( pos <= mid ) Update(2 * nod, currL, mid, pos, val);
     else              Update(2 * nod + 1, mid + 1, currR, pos, val);

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

int Query(int nod, int currL, int currR, int val){ // acest logN e mai bun decat (log^2)N de la AIB
     if (currL == currR) return currL;
     int mid = currL + (currR - currL) / 2;
     if (val <= tree[2 * nod]) return Query(2 * nod, currL, mid, val);
     else {
        val -= tree[2 * nod];
        return Query(2 * nod + 1, mid + 1, currR, val);
     }
}

int main() {
    f >> N;
    for (i = 1; i <= N; ++i) {
        Update(1, 1, N, i, 1); //am un spatiu liber pe intervalul i,i
        f >> A[i];
    }
    for (i = N; i >= 1; --i) {
        pozi = Query(1, 1, N, A[i]);
        Update(1, 1, N, pozi, 0);
        B[pozi] = i;
    }
    for (i = 1; i <= N; ++i)
        g << B[i] << '\n';
}