Cod sursa(job #3318276)

Utilizator Ristache_rocoRistea Octavian-Cristian Ristache_roco Data 27 octombrie 2025 19:13:24
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
using namespace std;

//1 = query pe un interval [x, y]
//2 = update x, y (ce e la x devine y)
//timp log(n) pt ambele
int sol;
void build(int nod, int st, int dr, int* v, int* aint) {
  if (st == dr) {
    aint[nod] = v[st];
  } else {
    int mid = (st + dr) / 2;
    build(2*nod, st, mid, v, aint);
    build(2*nod+1, mid+1, dr, v, aint);
    aint[nod] = aint[2*nod] + aint[2*nod+1];
  }
}
void update(int nod, int st, int dr, int pos, int val, int* aint) {
  if (st == dr) {
    aint[nod] = val;
  } else {
    int mid = (st + dr) / 2;
    if (pos <= mid) {
      update(2*nod, st, mid, pos, val, aint);
    } else {
      update(2*nod+1, mid+1, dr, pos, val, aint);
    }
    aint[nod] = aint[2*nod] + aint[2*nod+1];
  }
}
void query(int nod, int st, int dr, int val, int* aint) {
  if (st == dr) {

    sol= st; 
    return;
  }
  int mid = (st + dr) / 2;
  if (aint[2*nod] < val) {
    query(2*nod + 1, mid + 1, dr, val - aint[2*nod], aint);
  } else {
    query(2*nod, st, mid, val, aint);
  }
}
int main() {
  ifstream fin("schi.in");
  ofstream fout("schi.out");  
  int n, i;
  fin >> n;
  int v[n+1];
  int v2[n + 1];
  int rez[n+1];
  int aint[4*n+1];
  for (i = 1; i <= n; i++) {
    fin >> v[i];
    v2[i] = 1;
  }
  build(1, 1, n, v2, aint);
  for (i = n; i >= 1; i--) {
    query(1, 1, n,  v[i], aint);
    rez[sol] = i;
    update(1, 1, n, sol, 0, aint);
  }
  for (i = 1; i <= n; i++) {
    fout << rez[i] << endl;
  }
}