Cod sursa(job #2795600)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 6 noiembrie 2021 17:41:21
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

const int NMAX = 3e4;
const int LOGMAX = 15;

class FenwickTree {
private:
  int n;
  int data[2 * NMAX];

  static inline int lsb(int a) {
    return a & -a;
  }

public:
  FenwickTree(int n = 0) {
    this->n = n;
    memset(this->data, 0, sizeof(this->data));
  }

  void reset(int n = 0) {
    this->n = n;
    memset(this->data, 0, sizeof(this->data));
  }  

  void update(int index, int value) {
    for (int i = index; i <= n; i += lsb(i))
      data[i] += value;
  }

  int pointQuery(int index) {
    int ans = 0;
    for (int i = index; i >= 1; i -= lsb(i))
      ans += data[i];

    return 0;
  }

  int rangeQuery(int left, int right) {
    return pointQuery(right) - pointQuery(left - 1);
  }

  int upperBound(int target) {
    int index = 0;

    for (int exp = LOGMAX; exp >= 0; --exp) {
      int newIndex = index + (1 << exp);

      if (newIndex <= n && data[newIndex] <= target) {
        target -= data[newIndex];
        index = newIndex;
      }
    }

    return index;
  }

  int lowerBound(int target) {
    return upperBound(target - 1) + 1;
  }
};

int n;
int queries[1 + NMAX];
int ans[1 + NMAX];
 
FenwickTree bit;
 
int main() {
  inout("schi");
 
  in >> n;
  bit.reset(n);
  for (int i = 1; i <= n; ++i) {
    in >> queries[i];

    bit.update(i, 1);
  }
 
  for (int i = n; i > 0; --i) {
    int index = bit.lowerBound(queries[i]);

    ans[index] = i;

    bit.update(index, -1);
  }
 
  for (int i = 1; i <= n; ++i)
    out << ans[i] << '\n';

  return 0;
}