Cod sursa(job #3375596)

Utilizator Tudor_TapeTapu Tudor Cristian Tudor_Tape Data 12 noiembrie 2026 16:19:35
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

#define NMAX 30000

struct aint{
    pair<int, int> V[4*NMAX];
    int P[NMAX+5];
    int R[4*NMAX];
    void run() {
        V[1].first=1;
        V[1].second=NMAX;
        for (int i=0; i<=NMAX; i++) P[i]=0;
        for (int i=2; i<=4*NMAX; i++) {
            if (i%2==0) {
                V[i].first=V[i/2].first;
                V[i].second=V[i/2].first+((V[i/2].second-V[i/2].first)/2);
            }
            else {
                V[i].first=V[i/2].first+((V[i/2].second-V[i/2].first)/2)+1;
                V[i].second=V[i/2].second;
            }
            if (V[i].first==V[i].second && P[V[i].first]==0) {
                P[V[i].first]=i;
            }
        }
        P[1]=P[2]-1;
    }
    void update(int x, int poz, int i) {
        if (P[i]==poz) R[poz]=x;
        else {
            ///aici pui operatia pt aint
            ///in acest exemplu, pun suma
            R[poz]=R[poz*2]+R[poz*2+1];
        }
        if (poz!=1) update(x, poz/2, i);
    }
    int ans(int poz, int l1, int l2) {
        if (V[poz].first==V[poz].second) return R[poz];
        if (V[poz].first>=l1 && V[poz].second<=l2) return R[poz];
        int s1=0;
        if (l1<V[poz*2+1].first) s1=ans(poz*2, l1, l2);
        int s2=0;
        if (l2>V[poz*2].second) s2=ans(poz*2+1, l1, l2);
        return s1+s2;
    }
    int findpoz(int poz, int i) {
        if (V[poz].first==V[poz].second) return V[poz].first;
        int mij=(V[poz].first+V[poz].second)/2;
        int val=ans(1, V[poz].first, mij);
        if (val<i) return findpoz(poz*2+1, i-val);
        else return findpoz(poz*2, i);
    }
};

int X[30005];
int C[30005];
aint P;
int main() {
    int n, q;
    cin>>n>>q;
    P.run();
    for (int i=1; i<=n; i++) {
        cin>>X[i];
        P.update(1, P.P[i], i);
    }
    for (int i=n; i>=1; i--) {
        int v=P.findpoz(1, X[i]);
        C[v]=i;
        P.update(0, P.P[v], v);
        //cout<<i<<" "<<v<<"\n";
    }
    for (int i=1; i<=n; i++) {
        cout<<C[i]<<"\n";
    }
}