Submission #71971094

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>
#define INF 1010101010
#define KI_MAX (1 << 19) /* 524288 */
struct minmax_s {
  int min, max;
};
struct minmax_s merge(struct minmax_s a, struct minmax_s b) {
  return (struct minmax_s){
    a.min <= b.min ? a.min : b.min,
    a.max >= b.max ? a.max : b.max
  };
}
struct minmax_s ki[KI_MAX * 2 - 1];
void ki_set(int pos, int value) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define INF 1010101010

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

struct minmax_s {
	int min, max;
};

struct minmax_s merge(struct minmax_s a, struct minmax_s b) {
	return (struct minmax_s){
		a.min <= b.min ? a.min : b.min,
		a.max >= b.max ? a.max : b.max
	};
}

struct minmax_s ki[KI_MAX * 2 - 1];

void ki_set(int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] = merge(ki[pos], (struct minmax_s){ value, value });
	do {
		pos = (pos - 1) / 2;
		ki[pos] = merge(ki[pos * 2 + 1], ki[pos * 2 + 2]);
	} while (pos > 0);
}

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

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

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

int zac;
int zal[KI_MAX];

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

int N;
int C[KI_MAX], X[KI_MAX];

int left[KI_MAX], right[KI_MAX];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &C[i], &X[i]) != 2) return 1;
		zal[i] = X[i];
	}
	zal[N] = -INF;
	zal[N + 1] = INF * 2;
	qsort(zal, N + 2, sizeof(*zal), cmp);
	for (i = 1, zac = 1; i < N + 2; i++) {
		if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
	}
	for (i = 0; i < (int)(sizeof(ki) / sizeof(*ki)); i++) {
		ki[i] = (struct minmax_s){ INF, -INF };
	}
	ki_set(zaq(-INF), -1);
	ki_set(zaq(INF * 2), -1);
	for (i = 0; i < N; i++) {
		ki_set(zaq(X[i]), C[i]);
	}
	for (i = 0; i < zac; i++) left[i] = INF;
	for (i = 1; i < zac - 1; i++) {
		int no = i - 1, yes = zac - 1;
		while (no + 1 < yes) {
			int m = no + (yes - no) / 2;
			struct minmax_s minmax = ki_get(i, m + 1);
			if (minmax.min != minmax.max) yes = m; else no = m;
		}
		right[i] = left[yes] = zal[yes] - zal[i];
	}
	/* 左と同じ国のため、左にブロックされて来なかった所を埋める */
	for (i = 1; i < zac - 1; i ++) {
		if (left[i] >= INF && left[i - 1] < INF) left[i] = left[i - 1] + (zal[i] - zal[i - 1]);
	}
	for (i = 0; i < N; i++) {
		int pos = zaq(X[i]);
		printf("%d\n", left[pos] <= right[pos] ? left[pos] : right[pos]);
	}
	return 0;
}

/*

セグメント木で国の最小と最大を管理する
最小または最大が自分の出身国と異なる → 自分と違う出身国の選手が居る

→ TLEしたので、もうひと工夫
左(位置が小さい)の選手から見て右の選手の距離 → 右の選手から見て左の選手の距離も同じ
なので、右→左の探索は省略できる

*/

Submission Info

Judge Result