Cod sursa(job #2758620)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 11 iunie 2021 17:06:27
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 30000;
int n;
int v[NMAX];

struct elem{
    int hmin,poz,lazy;
};

class segtree{
private:
    elem t[3*NMAX];
public:
    void build(int nod,int st,int dr){
        if(st==dr){
            t[nod].hmin=v[st];
            t[nod].poz=st;
            t[nod].lazy=0;
            return ;
        }
        int mid=(st+dr)>>1;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        t[nod]=t[2*nod];
        if(t[2*nod+1].hmin<=t[2*nod].hmin){
            t[nod]=t[2*nod+1];
        }
    }
    void update(int nod,int st,int dr,int poz){
        if(st==dr){
            t[nod].hmin=INT_MAX;
            return ;
        }
        int mid=(st+dr)>>1;
        if(poz<=mid){
            update(2*nod,st,mid,poz);
            t[2*nod+1].lazy++;
            t[2*nod+1].hmin--;
        }else update(2*nod+1,mid+1,dr,poz);
        t[nod].hmin=t[2*nod].hmin;
        t[nod].poz=t[2*nod].poz;
        if(t[2*nod+1].hmin<=t[2*nod].hmin){
            t[nod].hmin=t[2*nod+1].hmin;
            t[nod].poz=t[2*nod+1].poz;
        }
        t[nod].hmin-=t[nod].lazy;

    }
    elem query(int nod,int st,int dr){
        return t[1];
    }

}sg;

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    sg.build(1,1,n);
    for(int i=1;i<=n;i++){
        printf("%d\n",sg.query(1,1,n).poz );
        int poz=sg.query(1,1,n).poz;
        sg.update(1,1,n,poz);
    }

    return 0;
}