Cod sursa(job #2017426)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 1 septembrie 2017 10:43:11
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

const int MAX = 3e4 + 1;

class Segmenet_Tree {
public:
  Segmenet_Tree(int n) {
    this -> n = n;
    arb.resize((MAX << 2));
  }

  void update(int target, int val) {
    _update(target, val, 1, this -> n, 1);
  }

  int query(int target_st, int target_dr) {
    return _query(target_st, target_dr, 1, this -> n, 1);
  }

private:
  int n;
  vector < short int > arb;

  void _update(int target, int val, int st, int dr, int nod) {
    if (st == dr) {
      arb[nod] = val;
      return;
    }

    int middle = (st + dr) >> 1;

    if (target <= middle) {
      _update(target, val, st, middle, nod << 1);
    }
    else {
      _update(target, val, middle + 1, dr, nod << 1 | 1);
    }

    arb[nod] = arb[nod << 1] + arb[nod << 1 | 1];
  }

  int _query(int target_st, int target_dr, int st, int dr, int nod) {
    if (target_st <= st and dr <= target_dr) {
      return arb[nod];
    }

    int middle = (st + dr) >> 1;
    int left = 0;
    int right = 0;
    if (target_st <= middle) {
      left = _query(target_st, target_dr, st, middle, nod << 1);
    }
    if (target_dr > middle) {
      right = _query(target_st, target_dr, middle + 1, dr, nod << 1 | 1);
    }

    return left + right;
  }
};

int main(int argc, char const *argv[]) {
  
  int n;
  cin >> n;

  Segmenet_Tree *T = new Segmenet_Tree(n);
  vector < short int > v (MAX);

  for (int i = 1; i <= n; i ++) {
    cin >> v[i];
    T -> update(i, 1);
  }

  vector < short int > sol (MAX);

  for (int i = n; i >= 1; i --) {
    int ans = 0;
    int s = 1e9;
    int seek_val = v[i];
    for (int bit = log2(n) + 1; bit >= 0; bit --) {
      if (ans + (1 << bit) > n) continue;

      int found_val = T -> query(1, (ans + (1 << bit)));
      if (found_val > seek_val) continue;
      
      if (found_val == seek_val) {
        s = ans + (1 << bit);
      }
      else {
        ans += (1 << bit);
      }
    }

    T -> update(s, 0);
    sol[s] = i;
  }

  for (int i = 1; i <= n; i ++) {
    cout << sol[i] << '\n';
  }

  delete T;
  return 0;
}