Cod sursa(job #2944648)

Utilizator db_123Balaban David db_123 Data 22 noiembrie 2022 19:55:58
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

struct SegmentTree {
	int n;
	vector<int> st;
	void resize(int n) {
		this->n = n;
		st.resize(4 * n+2,0);
	}
	int query(int start, int ending, int l, int r, int node) {
		if (start > r || ending < l) {
			return 0;
		}
		if (start >= l && ending <= r) {
			return st[node];
		}
		int mid = (start + ending) / 2;
		int q1 = query(start, mid, l, r, 2 * node);
		int q2 = query(mid + 1, ending, l, r, 2 * node + 1);
		return q1 + q2;
	}
	void update(int start, int ending, int node, int index, int value) {
		if (start == ending) {
			st[node] += value;
			return;
		}
        int mid = (start + ending) / 2;
		if (index <= mid) {
			update(start, mid, 2 * node , index, value);
		}
		else {
			update(mid + 1, ending, 2 * node + 1, index, value);
		}
		st[node] = st[node * 2] + st[node * 2 +1];
		return;
	}
};

int n;
SegmentTree seg;
vector<int> v;

void read() {
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
}

void solve() {
    seg.resize(n);
    for(int i=1;i<=n;i++) {
        seg.update(1,n,1,i,1);
    }
    vector<int> res(n+1);
    for(int i=n;i>0;i--) {
        int l=1,r=n,mid;
        while(l<=r) {
            mid=l+(r-l)/2;
            if(seg.query(1,n,1,mid,1)>=v[i]) {
                r=mid-1;
            }
            else {
                l=mid+1;
            }
        }
        res[l]=i;
        seg.update(1,n,1,l,-1);
    }
    for(int i=1;i<=n;i++) {
        cout<<res[i]<<"\n";
    }
}

int main() {

    read();
    solve();
    return 0;
}