Cod sursa(job #3371877)

Utilizator o_ctFerent Octavian o_ct Data 1 noiembrie 2026 14:42:21
Problema Schi Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int v[30001];
int aint[4*30001];
int n,s;
int r[30001];
void update(int nod,int left,int right,int i,int x)
{
    if(left==i && right==i)
    {
        aint[nod]=x;
        return;
    }
    int mij=(left+right)/2;
    if(i<=mij) update(nod<<1,left,mij,i,x);
    else update(nod<<1|1,mij+1,right,i,x);
    aint[nod]=aint[nod<<1]+aint[nod<<1|1];
}
int query(int nod,int left,int right,int a,int b)
{
    if(left>=a && right<=b) return aint[nod];
    int mij=(left+right)/2;
    int nodst=0,noddr=0;
    if(a<=mij) nodst=query(nod<<1,left,mij,a,b);
    if(b>mij) noddr=query(nod<<1|1,mij+1,right,a,b);
    return nodst+noddr;
}
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++) fin>>v[i];
    for(int i=n; i>=1; i--)
    {   s=query(1,1,n,1,v[i]);
        update(1,1,n,v[i]+s,1);
        while(r[v[i]+s]) s++;
        r[v[i]+s]=i;
    }
    for(int i=1; i<=n; i++) fout<<r[i]<<"\n";
    return 0;
}