Pagini recente » Cod sursa (job #2447454) | Cod sursa (job #57193) | Cod sursa (job #843829) | Cod sursa (job #2879014) | Cod sursa (job #1843700)
#include <bits/stdc++.h>
using namespace std;
struct nod{
nod *st, *dr;
unsigned prior;
int val, sz; } * nil = new nod { nullptr, nullptr, 0, 0, 0 };
ifstream f("schi.in");
ofstream g("schi.out");
void print_tree(nod *n){
if(n == nil) return;
print_tree(n->st);
g << n->val << '\n';
print_tree(n->dr); }
nod *recalc(nod *n){
n->sz = n->st->sz + n->dr->sz + 1;
return n; }
pair<nod*, nod*> split(nod *n, const int nr){
if(nr == 0) return make_pair(nil, n);
if(nr == n->sz) return make_pair(n, nil);
if(nr >= n->st->sz+1){
auto tmp = split(n->dr, nr - n->st->sz - 1);
n->dr = tmp.first;
return make_pair(recalc(n), tmp.second); }
else{
auto tmp = split(n->st, nr);
n->st = tmp.second;
return make_pair(tmp.first, recalc(n)); } }
nod *join(nod *st, nod *dr){
if(st == nil) return dr;
if(dr == nil) return st;
if(st->prior > dr->prior){
st->dr = join(st->dr, dr);
return recalc(st); }
else{
dr->st = join(st, dr->st);
return recalc(dr); } }
nod *insert(nod *n, const int poz, const int val){
assert(poz <= n->sz);
auto tmp = split(n, poz);
nod *mid = new nod { nil, nil, (unsigned)rand(), val, 1 };
return join(join(tmp.first, mid), tmp.second); }
int main(){
int n;
f >> n;
nod *rad = nil;
for(int i = 0, poz; i < n; ++i){
f >> poz;
rad = insert(rad, poz-1, i+1); }
print_tree(rad);
return 0; }