Cod sursa(job #2756601)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 1 iunie 2021 19:16:08
Problema Schi Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <cctype>
#include <algorithm>

#define NMAX 200000 //doua sute de mii

#define BUF_SIZE 1 << 17

using namespace std;

FILE *fin = fopen("schi.in", "r");
FILE *fout = fopen("schi.out", "w");

char buf[BUF_SIZE];
int pos = BUF_SIZE;

inline char nextch(){
    if(pos == BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos = 0;
    }

    return buf[pos++];
}

inline int read(){
    char ch = nextch();

    while( !isdigit(ch) ){
        ch = nextch();
    }

    int nr = 0;
    while( isdigit(ch) ){
        nr = nr * 10 + ch - '0';
        ch = nextch();
    }

    return nr;
}


int A, B;
int pozSterg;
int tree[4 * NMAX + 1];
int v[NMAX + 1];
int rez[NMAX + 1];

void creareArbore(int node, int left, int right){
    tree[node] = right - left + 1;

    if(left == right){
        return;
    }

    int mid = left + (right - left) / 2;
    creareArbore(node * 2, left, mid);
    creareArbore(node * 2 + 1, mid + 1, right);
}

int query(int node, int left, int right){
    if(A <= left && right <= B){
        return tree[node];
    }

    int mid = left + (right - left) / 2;
    int rez1 = 0, rez2 = 0;
    if(A <= mid){
        rez1 = query(node * 2, left, mid);
    }
    if(B >= mid + 1){
        rez2 = query(node * 2 + 1, mid + 1, right);
    }

    return rez1 + rez2;
}

void sterg(int node, int left, int right){
    if(left == right){
        tree[node] = 0;
        return;
    }

    int mid = left + (right - left) / 2;

    if(pozSterg <= mid){
        sterg(node * 2, left, mid);
    }
    else {
        sterg(node * 2 + 1, mid + 1, right);
    }

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

int main()
{
    int N;
    N = read();

    for(int i = 1; i <= N; i++){
        v[i] = read();
    }

    creareArbore(1, 1, N);

    for(int i = N; i >= 1; i--){

        int lo = 0;
        int hi = N + 1;

        while(hi - lo > 1){
            int mid = lo + (hi - lo) / 2;

            A = 1;
            B = mid; //[A, B] imi da intervalul pe care vreau suma
            if(query(1, 1, N) >= v[i]){
                hi = mid;
            }
            else{
                lo = mid;
            }
        }

        //raspunsul se afla in hi
        rez[ hi ] = i;

        pozSterg = hi;
        sterg(1, 1, N); //sterg hi
    }

    for(int i = 1; i <= N; i++){
        fprintf(fout, "%d\n", rez[i]);
    }

    return 0;
}