Pagini recente » Cod sursa (job #1959475) | Cod sursa (job #2699875) | Cod sursa (job #308116) | Cod sursa (job #1414994) | Cod sursa (job #853962)
Cod sursa(job #853962)
#include <fstream>
#define NMAX 500001
using namespace std;
ifstream input("algsort.in");
ofstream output("algsort.out");
unsigned int tree[1 << 20];
int N;
const unsigned int Infinit = 2147483648;
void delete_from_tree(int nod , int left , int right , const unsigned int value)
{
if (left == right)
{
tree[nod] = value;
}
else
{
int middle = (left + right) >> 1;
int left_son = nod << 1;
int right_son = left_son + 1;
if (tree[left_son] < tree[right_son]) delete_from_tree(left_son , left , middle , value);
else delete_from_tree(right_son , middle + 1, right , value);
tree[nod] = min(tree[left_son] , tree[right_son]);
}
}
void update_tree(int nod , int left , int right , const unsigned int value , int A)
{
if (left == right)
{
tree[nod] = value;
}
else
{
int middle = (left + right) >> 1;
int left_son = nod << 1;
int right_son = left_son + 1;
if (A <= middle) update_tree(left_son , left , middle , value , A);
if (A > middle) update_tree(right_son , middle+1 , right , value , A);
tree[nod] = min(tree[left_son] , tree[right_son]);
}
}
int main()
{
input >> N;
for (int i =1;i<=N;i++)
{
int x;
input >> x;
update_tree(1,1,N,x,i);
}
for (int i =1;i<=N;i++)
{
output << tree[1] << " ";
delete_from_tree(1,1,N,Infinit);
}
input.close();
output.close();
return 0;
}