Cod sursa(job #2945837)

Utilizator Stormtrooper-007Vartic Rihard Stormtrooper-007 Data 24 noiembrie 2022 10:39:07
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;
struct Stree
{
    vector<int>t;
    Stree(int n)
    {
       t.assign(4*n,0);
    }
    void Update(int nod, int l,int r,int pos,int val)
    {
        if(l==r)
        {
            t[nod]+=val;
            return;
        }
        int mid=(l+r)/2;
        if(pos<=mid)
        {
            Update(2*nod,l,mid,pos,val);
        }
        else
        {
            Update(2*nod+1,mid+1,r,pos,val);
        }
        t[nod]=t[2*nod]+t[2*nod+1];
    }
    int query(int nod, int l,int r,int x,int y)
    {int s=0;
        if(l>=x && r<=y)
        {
           // s=s+t[nod];
            return t[nod];
        }
        int mid=(l+r)/2;
        if(x<=mid)
        {
            s=s+query(2*nod,l,mid,x,y);
        }
        if(y>=mid+1)
        {
           s=s+query(2*nod+1,mid+1,r,x,y);
        }
        return s;
    }
};
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n;
    cin>>n;
    Stree h(n);
    vector<int>v(n);
    vector<int>ans(n+1);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    for(int i=n-1;i>=0;i--)
    {
        int l=0,r=n+2;
        while(l<r-1)
        {
            int mid=(l+r)/2;
            int a=h.query(1,1,n,1,mid);
           /// cout<<mid<<" "<<a<<'\n';
            if(mid-a>=v[i])
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        h.Update(1,1,n,r,1);
        ans[r]=i+1;
//Sussy baka
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}
//The imposter is sus