Cod sursa(job #2610006)

Utilizator bem.andreiIceman bem.andrei Data 3 mai 2020 23:47:37
Problema Schi Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
ifstream r("schi.in");
ofstream w("schi.out");
int v[30002], ai[100000], fin[30002], sum;
void update(int poz)
{
    ai[poz]=ai[poz*2]+ai[poz*2+1];
    if(poz==1)
    {
        return;
    }
    else
    {
        update(poz/2);
    }
}
void query(int st, int dr, int a, int b, int nod){
    if(st==a && dr==b){
        sum+=ai[nod];
    }
    else{
         if(st<=(a+b)/2){
            query(st, min(dr, (a+b)/2), a, (a+b)/2, nod*2);
         }
         if(dr>(a+b)/2){
            query(max(st, (a+b)/2+1), dr, (a+b)/2+1, b, nod*2+1);
         }
    }
}
int main()
{
    int n;
    r>>n;
    for(int i=1;i<=n;i++){
        r>>v[i];
    }
    int dim=1;
    while(dim<n)
    {
        dim*=2;
    }
    dim--;
    for(int i=n;i>0;i--){
        int st=v[i], dr=n, mij, p=v[i];
        while(st<=dr){
            mij=(st+dr)/2;
            sum=0;
            query(1+dim, mij+dim, dim+1, dim*2+1, 1);
            if(sum+v[i]<=mij){
                dr=mij-1;
                p=mij;
            }
            else{
                st=mij+1;
            }
        }
        fin[p]=i;
        ai[p+dim]=1;
        update((p+dim)/2);
    }
    for(int i=1;i<=n;i++){
        w<<fin[i]<<"\n";
    }
    return 0;
}