Cod sursa(job #3319762)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 3 noiembrie 2025 10:46:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

FILE *fin, *fout;
struct Treap{
  int idx;
  int val;
  int priority;
  int sz;
  Treap *left;
  Treap *right;
};
int get_sz(Treap *t) {
  if(t == nullptr)
    return 0;
  return t->sz;
}
void rebuild(Treap *t) {
  if(t == nullptr)
    return;
  t->sz = 1 + get_sz(t->left) + get_sz(t->right);
}
std::pair<Treap*, Treap*> split(Treap* t, int x) {
  if(t == nullptr) {
    return {nullptr, nullptr};
  }else if(get_sz(t->left) >= x) {
    auto [first, second] = split(t->left, x);
    t->left = second;
    rebuild(t);
    return {first, t};
  }else {
    auto[first, second] = split(t->right, x - get_sz(t->left) - 1);
    t->right = first;
    rebuild(t);
    return {t, second};
  }
}
Treap* merge(Treap* l, Treap* r) {
  if(l == nullptr)
    return r;
  else if(r == nullptr)
    return l;
  else if(l->priority > r->priority){
    l->right = merge(l->right, r);
    rebuild(l);
    return l;
  }else {
    r->left = merge(l, r->left);
    rebuild(r);
    return r;
  }
}
Treap* insert(Treap* t, int poz, int val) {
  Treap* nd = new Treap{
    .idx = poz,
    .val = val,
    .priority = rand(),
    .sz = 1,
    .left = nullptr,
    .right = nullptr
  };
  auto [first, second] = split(t, poz);
  return merge(merge(first, nd), second);
}
void dump(Treap *t) {
  if(t == nullptr)
    return;
  rebuild(t);
  dump(t->left);
  fprintf(fout, "%d\n", t->val);
  dump(t->right);
}
int main(){
  fin = fopen("schi.in", "r");
  fout = fopen("schi.out", "w");
  int n;
  fscanf(fin, "%d", &n);
  Treap *t = nullptr;
  for( int i = 0; i < n; i++ ) {
    int x;
    fscanf(fin, "%d", &x);
    x--;
    t = insert(t, x, i + 1);
  }
  dump(t);
  fclose(fin);
  fclose(fout);
  return 0;
}