Submission #66889102

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KI_MAX (1 << 19) /* 524288 */
int ki[KI_MAX * 2 - 1];
void ki_set(int pos, int value) {
  pos += KI_MAX - 1;
  ki[pos] = value;
  do {
    int a, b;
    pos = (pos - 1) / 2;
    a = ki[pos * 2 + 1];
    b = ki[pos * 2 + 2];
    ki[pos] = a >= b ? a : b;
  } while (pos > 0);
}
int ki_get_i(int idx, int ss, int se, int qs, int qe) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KI_MAX (1 << 19) /* 524288 */

int ki[KI_MAX * 2 - 1];

void ki_set(int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] = value;
	do {
		int a, b;
		pos = (pos - 1) / 2;
		a = ki[pos * 2 + 1];
		b = ki[pos * 2 + 2];
		ki[pos] = a >= b ? a : b;
	} while (pos > 0);
}

int ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return -1;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_get_i(idx * 2 + 1, ss, sm, qs, qe);
		int r = ki_get_i(idx * 2 + 2, sm, se, qs, qe);
		return l >= r ? l : r;
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int N, D, R;
int H[512345];

struct idxpos_s {
	int idx, pos;
} idxpos[512345];

/* pos (H) の昇順 */
int cmp(const void* x, const void* y) {
	struct idxpos_s a = *(const struct idxpos_s*)x, b = *(const struct idxpos_s*)y;
	return a.pos < b.pos ? -1 : a.pos > b.pos;
}

int eachans[512345];

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d%d%d", &N, &D, &R) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &H[i]) != 1) return 1;
		idxpos[i].idx = i;
		idxpos[i].pos = H[i];
	}
	qsort(idxpos, N, sizeof(*idxpos), cmp);
	/* すべての移動先を -1 に初期化する */
	memset(ki, -1, sizeof(ki));
	for (i = 0; i < N; i++) {
		/* D 個前の足場を移動可能な場所として加える */
		if (i - D >= 0) {
			ki_set(idxpos[i - D].idx, eachans[i - D]);
		}
		eachans[i] = ki_get(idxpos[i].idx - R, idxpos[i].idx + R + 1) + 1;
		if (eachans[i] > ans) ans = eachans[i];
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result