Cod sursa(job #2775555)

Utilizator TraianQTraianQ TraianQ Data 16 septembrie 2021 11:26:50
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
using namespace std;
struct Arb
{
    int val,poz,lazy;
}t[90005];
int n,v[30005],poz;
void build(int node,int st,int dr)
{
    if(st==dr)
    {
       t[node].val=v[st];
       t[node].poz=st;
       t[node].lazy=0;
    }
    else
    {
        int mij=(st+dr)/2;
        build(2*node,st,mij);
        build(2*node+1,mij+1,dr);
        t[node]=t[2*node];
        if(t[2*node+1].val<=t[2*node].val)
            t[node]=t[2*node+1];
    }
}
void propagate(int node,int st,int dr)
{
    t[node].val-=t[node].lazy;
    if(st!=dr) {
        t[2*node].lazy += t[node].lazy;
        t[2*node+1].lazy += t[node].lazy;
    }
    t[node].lazy=0;
}
void update(int node,int st,int dr)
{
    propagate(node,st,dr);
    if(st==dr)
    {
       t[node].val=2e9;
    }
    else
    {
        int mij=(st+dr)/2;
        if(poz<=mij)
        {
            update(2*node,st,mij);
            t[2*node+1].lazy++;
            propagate(2*node+1,mij+1,dr);
        }
        else {
            update(2*node+1,mij+1,dr);
            propagate(2*node,st,mij);
        }
        t[node]=t[2*node];
        if(t[2*node+1].val<=t[2*node].val)
            t[node]=t[2*node+1];
    }
}
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<t[1].poz<<"\n";
        poz=t[1].poz;
        update(1,1,n);
    }
    return 0;
}