結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー danielsun3164
提出日時 2025-01-25 04:49:19
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,128 ms / 2,000 ms
コード長 3,533 bytes
コンパイル時間 6,742 ms
コンパイル使用メモリ 87,300 KB
実行使用メモリ 77,464 KB
最終ジャッジ日時 2025-01-25 04:50:08
合計ジャッジ時間 30,233 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), a = scanner.nextInt(), b = scanner.nextInt();
			Integer[] x = IntStream.range(0, n).map(i -> scanner.nextInt()).boxed().toArray(Integer[]::new);
			RangeUnionFind uf = new RangeUnionFind(n);
			IntStream.range(0, n).forEach(i -> {
				int l = lowerBound(x, x[i] + a), r = lowerBound(x, x[i] + b + 1);
				uf.rangeUnite(l, r);
			});
			IntStream.range(0, n).forEach(i -> {
				int l = lowerBound(x, x[i] + a), r = lowerBound(x, x[i] + b + 1);
				if (l != r) {
					uf.unite(l, i);
				}
			});
			StringBuilder sb = new StringBuilder();
			IntStream.range(0, n).forEach(i -> sb.append(uf.size(i)).append(System.lineSeparator()));
			System.out.print(sb.toString());
			System.out.flush();
		}
	}

	private static int lowerBound(Integer[] x, int value) {
		return ~Arrays.binarySearch(x, value, (a, b) -> (a.compareTo(b) >= 0) ? 1 : -1);
	}

	/**
	 * Range Union Find<br/>
	 * https://github.com/NyaanNyaan/library/blob/master/data-structure/range-union-find.hpp を参考に作成
	 */
	private static class RangeUnionFind {

		final int[] data, left, right;

		/**
		 * コンストラクター
		 *
		 * @param n
		 */
		RangeUnionFind(int n) {
			data = new int[n];
			Arrays.fill(data, -1);
			left = IntStream.range(0, n).toArray();
			right = IntStream.rangeClosed(1, n).toArray();
		}

		/**
		 * kのリーダーを取得する
		 *
		 * @param k
		 * @return kのリーダー
		 */
		int find(int k) {
			return (data[k] < 0) ? k : (data[k] = find(data[k]));
		}

		/**
		 * xとyをマージする
		 *
		 * @param x
		 * @param y
		 * @return すでにマージ済みの場合はfalse、それ以外の場合はtrue
		 */
		boolean unite(int x, int y) {
			return unite(x, y, null);
		}

		/**
		 * xとyをマージする
		 *
		 * @param x
		 * @param y
		 * @param f マージ後の追加処理
		 * @return すでにマージ済みの場合はfalse、それ以外の場合はtrue
		 */
		boolean unite(int x, int y, IntBiConsumer f) {
			if ((x = find(x)) == (y = find(y))) {
				return false;
			}
			if (data[x] > data[y]) {
				int t = x;
				x = y;
				y = t;
			}
			data[x] += data[y];
			data[y] = x;
			left[x] = Math.min(left[x], left[y]);
			right[x] = Math.max(right[x], right[y]);
			if (null != f) {
				f.accept(x, y);
			}
			return true;
		}

		/**
		 * [l,r)の範囲をマージする
		 *
		 * @param l
		 * @param r
		 */
		void rangeUnite(int l, int r) {
			rangeUnite(l, r, null);
		}

		/**
		 * [l,r)の範囲をマージする
		 *
		 * @param l
		 * @param r
		 * @param f マージ後の追加処理
		 */
		void rangeUnite(int l, int r, IntBiConsumer f) {
			if ((l = Math.max(0, l)) >= (r = Math.min(r, data.length))) {
				return;
			}
			int m;
			while ((m = right[find(l)]) < r) {
				unite(l, m, f);
			}
		}

		/**
		 * kが所属するグループの要素数を取得する
		 *
		 * @param k
		 * @return kが所属するグループの要素数
		 */
		int size(int k) {
			return -data[find(k)];
		}

		/**
		 * xとyは同じグループに所属するかを取得する
		 *
		 * @param x
		 * @param y
		 * @return xとyは同じグループに所属するか
		 */
		@SuppressWarnings("unused")
		boolean same(int x, int y) {
			return find(x) == find(y);
		}

	}

	private static interface IntBiConsumer {
		void accept(int a, int b);
	}
}
0