結果
問題 | 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 |
ソースコード
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); } }