Submission #70727491

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 BIT_MAX 512345
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= BIT_MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos++;
  while (pos > 0) {
    sum += bit_table[pos - 1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define BIT_MAX 512345

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= BIT_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int N;
int X[BIT_MAX];

int order[BIT_MAX];
int score[BIT_MAX];

int get_id(int query) {
	int l = 0, r = N;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (order[m] == query) return m;
		else if (order[m] < query) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found\n", query);
	exit(42);
}

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &X[i]) != 1) return 1;
	}
	memcpy(order, X, sizeof(*X) * (N + 1));
	qsort(order, N + 1, sizeof(*order), cmp);
	bit_add(get_id(X[0]), 1);
	bit_add(get_id(X[1]), 1);
	score[get_id(X[0])] = X[1] - X[0];
	score[get_id(X[1])] = X[1] - X[0];
	ans = (X[1] - X[0]) * 2;
	printf("%d\n", ans);
	for (i = 2; i <= N; i++) {
		int id = get_id(X[i]);
		int cur = bit_sum(id);
		int l_l, l_ge, r_le, r_g;
		int ld, rd;
		/* 左隣の人の位置を求める */
		l_l = -1;
		l_ge = id;
		while (l_l + 1 < l_ge) {
			int m = l_l + (l_ge - l_l) / 2;
			if (bit_sum(m) < cur) l_l = m; else l_ge = m;
		}
		/* 右隣の人の位置を求める */
		r_le = id;
		r_g = N + 1;
		while (r_le + 1 < r_g) {
			int m = r_le + (r_g - r_le) / 2;
			if (bit_sum(m) > cur) r_g = m; else r_le = m;
		}
		/* 最短距離を更新する */
		if (r_g <= N) {
			/* 右隣の人が存在する */
			ld = order[id] - order[l_ge];
			rd = order[r_g] - order[id];
			if (score[l_ge] > ld) {
				ans -= score[l_ge] - ld;
				score[l_ge] = ld;
			}
			if (score[r_g] > rd) {
				ans -= score[r_g] - rd;
				score[r_g] = rd;
			}
			ans += (score[id] = ld <= rd ? ld : rd);
		} else {
			/* 右隣の人が存在しない */
			ld = order[id] - order[l_ge];
			if (score[l_ge] > ld) {
				ans -= score[l_ge] - ld;
				score[l_ge] = ld;
			}
			ans += (score[id] = ld);
		}
		printf("%d\n", ans);
		bit_add(id, 1);
	}
	return 0;
}

Submission Info

Judge Result