Cod sursa(job #2503525)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 3 decembrie 2019 12:38:55
Problema Schi Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

struct rav{
	int mini = INT_MAX, ad = 0;
};

int n;
rav tre[120041];
int v;
void rec(int a, int b, int ad = 0, int lt = 1, int rt = n, int p = 1){
	int nad = ad+tre[p].ad;
	// cout << a << " " << b << " " << lt << " " << rt << "\n";
	if(lt == a && rt == b && tre[p].mini+nad >= v){
		tre[p].ad++;
		// cout << lt << " " << rt << "\n";
	}else if(lt != rt){
		int m = (lt+rt)/2;
		if(a >= lt && b <= m){
			rec(a, b, nad, lt, m, 2*p);
		}else if(a >= m+1 && b <= rt){
			rec(a, b, nad, m+1, rt, 2*p+1);
		}else{
			rec(a, m, nad, lt, m, 2*p);
			rec(m+1, b, nad, m+1, rt, 2*p+1);
		}
	}
}

void jus(int a){
	int lt = 1, rt = n;
	int p = 1, ad = tre[1].ad;
	while(lt != rt){
		int m = (lt+rt)/2;
		tre[p].mini = min(tre[p].mini, v-ad);
		if(a <= m){
			rt = m;
			p = 2*p;
		}else{
			lt = m+1;
			p = 2*p+1;
		}
		ad += tre[p].ad;
	}
	tre[p].mini = v-ad;
}

int sol[30041];
void hep(int ad = 0, int lt = 1, int rt = n, int p = 1){
	int nad = ad + tre[p].ad;
	if(lt == rt){
		sol[tre[p].mini+nad] = lt;
	}else{
		int m = (lt+rt)/2;
		hep(nad, lt, m, 2*p);
		hep(nad, m+1, rt, 2*p+1);
	}
}

int main(){
	fin >> n;
	for(int i = 1; i <= n; i++){
		fin >> v;
		rec(1, i-1);
		jus(i);
	}
	hep();
	
	for(int i = 1; i <= n; ++i){
		fout << sol[i] << "\n";
	}
	return 0;
}