19646 - Random Generator

 

19646번: Random Generator

 

#include <stdio.h>

const int LN = 2e5;

int R;
int R_ARR[LN];
int tree[LN * 3 + 10];
int N;

int push(int n, int s, int e, int t, int v) {
  if (s == e && s == t) {
    tree[n] = v;

    return tree[n];
  }

  if (t < s || e < t) { return tree[n]; }

  int m = (s + e) / 2;

  push(n * 2, s, m, t, v);
  push(n * 2 + 1, m + 1, e, t, v);

  tree[n] = tree[n * 2] + tree[n * 2 + 1];

  return tree[n];
}

int query(int n, int s, int e, int qs, int qe) {
  if (qe < s || e < qs) { return 0; }
  if (qs <= s && e <= qe) { return tree[n]; }

  int m = (s + e) / 2;

  return query(n * 2, s, m, qs, qe) + query(n * 2 + 1, m + 1, e, qs, qe);
}

void bs(int s, int e, int target) {
  if (s > e) { return; }

  int m = (s + e) / 2;
  int q_res = query(1, 1, N, 1, m);

  if (q_res >= target) {
    R = m;
    bs(s, m - 1, target);
  } else {
    bs(m + 1, e, target);
  }
}

void init() {
  scanf("%d", &N);

  for (int n = 1; n <= N; ++n) {
    int v;
    
    scanf("%d", &v);

    push(1, 1, N, n, v);
  }
}

void cal() {
  for (int n = 1; n <= N; ++n) {
    int t;

    scanf("%d", &t);

    bs(1, N, t);

    R_ARR[n]= R;

    push(1, 1, N, R, 0);
  }
}

void print() {
  for (int n = 1; n <= N; ++n) {
    printf("%d ", R_ARR[n]);
  }
}

int main(void) {
  // freopen("19646.txt", "r", stdin);

  init();

  cal();

  print();

  return 0;
}

 

앞에 몇 개 있는지 갯수 셀 때 세그먼트 트리 세는거 같당