Cod sursa(job #2330198)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 28 ianuarie 2019 01:39:52
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define N 30005
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int a[N],m[4*N],r[N],v[N],n,x,y;
void cm(int l, int r, int nod){
    if(l==r){
        m[nod]=l;
        return;
    }
    int mij=(l+r)/2;
    cm(l, mij, 2*nod);
    cm(mij+1, r, 2*nod+1);
    m[nod]=min(m[2*nod],m[2*nod+1]);
}
void updm(int l, int r, int nod){
    if(l==r){
        m[nod]=INT_MAX;
        return;
    }
    int mij=(l+r)/2;
    if(y<=mij)
        updm(l,mij,2*nod);
    else updm(mij+1,r,2*nod+1);
    m[nod]=min(m[nod*2],m[nod*2+1]);
}
void qm(int l, int r, int nod){
    if(x<=l && r<=n){
        y=min(y,m[nod]);
        return;
    }
    int mij=(l+r)/2;
    if(x<=mij)
        qm(l,mij,2*nod);
    qm(mij+1,r,2*nod+1);
}
void upda(int i){
    while(i<=n){
        ++a[i];
        i+=(i&(-i));
    }
}
int qa(int i){
    int s=0;
    while(i){
        s+=a[i];
        i-=(i&(-i));
    }
    return s;
}
int main(){
    int i;
    in>>n;
    for(i=1; i<=n; ++i)
        in>>v[i];
    cm(1,n,1);
    for(i=n; i>0; --i){
        y=INT_MAX;
        x=qa(v[i])+v[i];
        qm(1,n,1);
        r[y]=i;
        upda(v[i]);
        updm(1,n,1);
    }
    for(i=1; i<=n; ++i)
        out<<r[i]<<"\n";
    return 0;
}