3006 - 터보소트

 

3006번: 터보소트

 

#include <stdio.h>

const int LN = 1e5;

int N;
int idxs[LN + 10];
int tree[LN * 3 + 10];

int seg_init(int n, int s, int e) {
  if (s == e) {
    return tree[n] = 1;
  }

  int m = (s + e) / 2;

  return tree[n] = seg_init(n * 2, s, m) + seg_init(n * 2 + 1, m + 1, e);
}

void update(int n, int s, int e, int t, int v) {
  if (t < s || e < t) { return; }
  if (s == e && e == t) {
    tree[n] = 0;
    
    return;
  }

  int m = (s + e) / 2;

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

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

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 init() {
  int idx;

  scanf("%d", &N);

  seg_init(1, 1, N);

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

    idxs[idx] = n;
  }
}

void cal() {
  int s = 1, e = N;
  int flag = 0, idx;

  while (s <= e) {
    if (flag++ % 2 == 0) {
      update(1, 1, N, idxs[s], 0);
      printf("%d\n", query(1, 1, N, 1, idxs[s++]));
    } else {
      update(1, 1, N, idxs[e], 0);
      printf("%d\n", query(1, 1, N, idxs[e--], N));
    }
  }
}

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

  init();

  cal();

  return 0;
}

 

쉽다 쉬워