1306 - 달려라 홍준

 

1306번: 달려라 홍준

 

#include <stdio.h>

const int MAX_NUM = 1e6 + 10;
const int NODE = 1e6;

int tree[NODE * 3];

int N, M;
int sp, ep;

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

    return tree[n];
  }

  int m = (s + e) / 2;

  if (t <= m) {
    push(n * 2, s, m, t, v);
  } else {
    push(n * 2 + 1, m + 1, e, t, v);
  }

  int l = n * 2; int r = l + 1;

  tree[n] = tree[l] > tree[r] ? tree[l] : tree[r];

  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;

  int l = query(n * 2, s, m, qs, qe);
  int r = query(n * 2 + 1, m + 1, e, qs, qe);

  return l > r ? l : r;
}

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

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

    scanf("%d", &t);

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

void print() {
  sp = 1; ep = 2 * M - 1;

  while (ep <= N) {
    printf("%d ", query(1, 1, N, sp, ep));

    sp++;
    ep++;
  }
}

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

  init();

  print();

  return 0;
}

 

힙으로 푸신 사람들도 있던데,,,

 

이게 더 편하지 않나 ?