Cod sursa(job #2681639)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 5 decembrie 2020 23:53:17
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <cassert>

const int NMAX = 3e4;

int n;

int seg_tree[3 * NMAX];

int a[1 + NMAX];

int order[1 + NMAX];

void update(int node, int left, int right, int ind, int val) {
  if (left == right) {
    assert(left == ind);
    seg_tree[node] = val;
    return;
  }

  int mid = (left + right) / 2;
  int left_child = 2 * node;
  int right_child = 2 * node + 1;

  if (ind <= mid)
    update(left_child, left, mid, ind, val);
  else
    update(right_child, mid + 1, right, ind, val);

  seg_tree[node] = seg_tree[left_child] + seg_tree[right_child];
}

int query(int node, int left, int right, int q_left, int q_right) {
  if (left > q_right || right < q_left)
    return 0;

  if (q_left <= left && right <= q_right)
    return seg_tree[node];

  int mid = (left + right) / 2;
  int left_child = 2 * node;
  int right_child = 2 * node + 1;

  return query(left_child, left, mid, q_left, q_right) + query(right_child, mid + 1, right, q_left, q_right);
}

void read() {
  std::ifstream in("schi.in");

  in >> n;

  for (int i = 1; i <= n; ++i)
    in >> a[i];

  in.close();
}

int main() {
  read();

  for (int i = n; i >= 1; --i) {
    int prev_sum = query(1, 1, n, 1, a[i]);

    int new_pos = a[i] + prev_sum;
    int new_sum = query(1, 1, n, 1, new_pos);

    while (new_sum != prev_sum) {
      new_pos = a[i] + new_sum;
      prev_sum = new_sum;
      new_sum = query(1, 1, n, 1, new_pos);
    }

    update(1, 1, n, new_pos, 1);
    order[new_pos] = i;
  }

  std::ofstream out("schi.out");
  for (int i = 1; i <= n; ++i)
    out << order[i] << '\n';

  out.close();
  return 0;
}