Cod sursa(job #2017433)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 1 septembrie 2017 11:18:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 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) {
    return _query(target, 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, int st, int dr, int nod) {
    if (st == dr) {
      return arb[nod];
    }

    int middle = (st + dr) >> 1;
    int left = 0;
    int right = 0;

    if (target <= middle) {
      left = _query(target, st, middle, nod << 1);
    }
    else {
      left = arb[nod << 1];
      right = _query(target, 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(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;
}