Pagini recente » Cod sursa (job #1794670) | Cod sursa (job #397268) | Cod sursa (job #2178259) | Cod sursa (job #384534) | Cod sursa (job #1826569)
//Arbori de intervale - Sortare
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");
#define DMAX 500000
int N;
int ArbInt[DMAX*4];
void update(int nod, int st, int dr, int poz, int val) {
if(st == dr) {
ArbInt[nod] = val;
return;
}
int mid = (st + dr)/2;
if(poz <= mid)
update(2*nod, st, mid, poz, val);
else
update(2*nod + 1, mid + 1, dr, poz, val);
ArbInt[nod] = min(ArbInt[2*nod], ArbInt[2*nod + 1]);
}
int query(int nod, int st, int dr, int val) {
if(st == dr)
return st;
int mid = (st + dr)/2;
if(ArbInt[2*nod] == val)
return query(2*nod, st, mid, val);
else
return query(2*nod + 1, mid + 1, dr, val);
}
int main()
{
int i;
int x;
fin>>N;
for(i = 1 ; i <= N ; i++) {
fin>>x;
update(1, 1, N, i, x);
}
for(i = 1 ; i <= N ; i++) {
fout<<ArbInt[1]<<" ";
x = query(1, 1, N, ArbInt[1]);
update(1, 1, N, x, INT_MAX);
}
fin.close();
fout.close();
return 0;
}