Cod sursa(job #3259915)

Utilizator iustincmbMaican Iustin iustincmb Data 28 noiembrie 2024 15:09:53
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>
using namespace std;
int lazy[120050];
int ras[30005];
struct node{
    int val, val1;
    int poz;
} aint[120050];
int v[30050];
void propagate(int node, int st, int dr){
    if(st<dr){
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    if(st<=dr){
        aint[node].val+=lazy[node];
        aint[node].val1+=lazy[node];
    }
    lazy[node]=0;
}
void build(int node, int st, int dr){
    if(st==dr){
        aint[node].val=v[st];
        aint[node].val1=v[st];
        aint[node].poz=st;
    }
    else{
        int mid=(st+dr)/2;
        build(2*node, st, mid);
        build(2*node+1, mid+1, dr);
        if(aint[2*node].val<aint[2*node+1].val)
            aint[node].poz=aint[2*node].poz;
        else
            aint[node].poz=aint[2*node+1].poz;
        aint[node].val=min(aint[2*node].val, aint[2*node+1].val);
        aint[node].val1=max(aint[2*node].val1, aint[2*node+1].val1);
    }
}
void update(int node, int st, int dr, int a, int b, int val){
    propagate(node, st, dr);
    if(a<=st && dr<=b)
        lazy[node]+=val;
    else{
        int mid=(st+dr)/2;
        if(a<=mid)
            update(2*node, st, mid, a, b, val);
        if(mid+1<=b)
            update(2*node+1, mid+1, dr, a, b, val);
        propagate(2*node, st, dr);
        propagate(2*node+1, mid+1, dr);
        if(aint[2*node].val<aint[2*node+1].val)
            aint[node].poz=aint[2*node].poz;
        else
            aint[node].poz=aint[2*node+1].poz;
        aint[node].val=min(aint[2*node].val, aint[2*node+1].val);
        aint[node].val1=max(aint[2*node].val1, aint[2*node+1].val1);
    }
}
int min1=30001, poz1, max1=0;
void query(int node, int st, int dr, int a, int b){
    propagate(node, st, dr);
    if(a<=st && dr<=b){
        if(aint[node].val<min1){
            min1=aint[node].val;
            poz1=aint[node].poz;
        }
        max1=max(max1, aint[node].val1);
    }
    else{
        int mid=(st+dr)/2;
        if(a<=mid)
            query(2*node, st, mid, a, b);
        if(mid+1<=b)
            query(2*node+1, mid+1, dr, a, b);
    }
}
int main(){
    ifstream cin ("schi.in");
    ofstream cout ("schi.out");
    int n, max2=0, l=0, cnt3=0;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> v[i];
        max2=max(max2, v[i]);
    }
    build(1, 1, n);
    for(int t=1; t<=n; t++){
        max1=0;
        query(1, 1, n, 1, n);
        min1=32;
        query(1, 1, n, 1, n);
        update(1, 1, n, poz1+1, n, -1);
        cout << poz1 << '\n';
        update(1, 1, n, poz1, poz1, 2100000000-v[poz1]);
        query(1, 1, n, poz1, poz1);
        ras[++l]=poz1;
    }
    return 0;
}