Pagini recente » Cod sursa (job #1378802) | Cod sursa (job #247998) | Cod sursa (job #1647226) | Cod sursa (job #262721) | Cod sursa (job #1843702)
#include <bits/stdc++.h>
using namespace std;
struct nod{
int st, dr, sz;
unsigned prior; };
nod nods[(int)3e4 + 100] = {};
ifstream f("schi.in");
ofstream g("schi.out");
void print_tree(int n){
if(!n) return;
print_tree(nods[n].st);
g << n << '\n';
print_tree(nods[n].dr); }
int recalc(int n){
nods[n].sz = 1 + nods[nods[n].st].sz + nods[nods[n].dr].sz;
return n; }
pair<int, int> split(int n, const int nr){
if(nr == 0) return make_pair(0, n);
if(nr == nods[n].sz) return make_pair(n, 0);
if(nr >= nods[nods[n].st].sz+1){
auto tmp = split(nods[n].dr, nr - nods[nods[n].st].sz - 1);
nods[n].dr = tmp.first;
return make_pair(recalc(n), tmp.second); }
else{
auto tmp = split(nods[n].st, nr);
nods[n].st = tmp.second;
return make_pair(tmp.first, recalc(n)); } }
int join(int st, int dr){
if(st == 0) return dr;
if(dr == 0) return st;
if(nods[st].prior > nods[dr].prior){
nods[st].dr = join(nods[st].dr, dr);
return recalc(st); }
else{
nods[dr].st = join(st, nods[dr].st);
return recalc(dr); } }
int insert(int n, const int poz, const int val){
auto tmp = split(n, poz);
nods[val].prior = rand();
nods[val].sz = 1;
return join(join(tmp.first, val), tmp.second); }
int main(){
int n;
f >> n;
int rad = 0;
for(int i = 0, poz; i < n; ++i){
f >> poz;
rad = insert(rad, poz-1, i+1); }
print_tree(rad);
return 0; }