結果

問題 No.1170 Never Want to Walk
ユーザー danielsun3164
提出日時 2025-01-03 22:14:06
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 4,852 bytes
コンパイル時間 2,903 ms
コンパイル使用メモリ 92,696 KB
実行使用メモリ 802,756 KB
最終ジャッジ日時 2025-01-03 22:15:52
合計ジャッジ時間 46,929 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other AC * 19 TLE * 12 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.Scanner;
import java.util.function.IntConsumer;
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);
			DivideInterval di = new DivideInterval(n);
			UnionFind uf = new UnionFind(di.b << 1);
			int[] num = new int[di.b << 1];
			Arrays.fill(num, 0);
			IntStream.range(0, n).forEach(i -> num[di.b + i] = 1);

			IntBiConsumer f = (p, q) -> num[p] += num[q];
			IntConsumer rec = new IntConsumer() {
				@Override
				public void accept(int c) {
					if (di.b <= c) {
						return;
					}
					for (int t = 0; t < 2; t++) {
						if (!uf.same(c, (c << 1) + t)) {
							uf.unite(c, (c << 1) + t, f);
							accept((c << 1) + t);
						}
					}
				}
			};
			IntStream.range(0, n).forEach(i -> {
				int l = lowerBound(x, x[i] + a), r = lowerBound(x, x[i] + b + 1);
				di.apply(l, r, j -> {
					uf.unite(i + di.b, j, f);
					rec.accept(j);
				});
			});
			StringBuilder sb = new StringBuilder();
			IntStream.range(0, n).forEach(i -> sb.append(num[uf.find(di.b + 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);
	}

	/**
	 * セグ木状に区間を分割したときの処理<br/>
	 * https://github.com/NyaanNyaan/library/blob/master/data-structure/divide-interval.hpp を参考に作成
	 *
	 * 2*B 個の頂点を持つグラフを考える。<br/>
	 * B+i が元のグラフの頂点 i に対応する
	 */
	private static class DivideInterval {

		final int n, b;

		DivideInterval(int n) {
			this.n = n;
			int b = 1;
			while (b < n) {
				b <<= 1;
			}
			this.b = b;
		}

		/**
		 * O(N) 根から葉方向へ push する
		 *
		 * @param f f(p,c) : p -> c へ伝播
		 */
		@SuppressWarnings("unused")
		void push(IntBiConsumer f) {
			for (int p = 1; p < b; p++) {
				f.accept(p, p << 1);
				f.accept(p, (p << 1) | 1);
			}
		}

		/**
		 * O(N) 葉から根の方向に update する
		 *
		 * @param f f(p, c1, c2) : c1 と c2 の結果を p へマージ
		 */
		@SuppressWarnings("unused")
		void update(IntTriConsumer f) {
			for (int p = b - 1; p > 0; p--) {
				f.accept(p, p << 1, (p << 1) | 1);
			}
		}

		/**
		 * [l, r) に対応する index の列を返す
		 *
		 * 順番は左から右へ並んでいる<br/>
		 * 例: [1, 11) : [1, 2), [2, 4), [4, 8), [8, 10), [10, 11)
		 *
		 * @param l
		 * @param r
		 * @return [l, r) に対応する index の列
		 */
		int[] range(int l, int r) {
			if (!((0 <= l) && (l <= r) && (r <= n))) {
				throw new IllegalArgumentException("l=" + l + ", r=" + r + ", n=" + n);
			}
			int[] il = new int[n], ir = new int[n];
			int lIndex = 0, rIndex = 0;
			for (l += b, r += b; l < r; l >>= 1, r >>= 1) {
				if (1 == (1 & l)) {
					il[lIndex++] = l++;
				}
				if (1 == (1 & r)) {
					ir[rIndex++] = --r;
				}
			}
			int[] result = new int[lIndex + rIndex];
			System.arraycopy(il, 0, result, 0, lIndex);
			for (int i = rIndex - 1; i >= 0; i--) {
				result[lIndex++] = ir[i];
			}
			return result;
		}

		/**
		 * [l, r) に対応する index に対してクエリを投げる(区間は昇順)
		 *
		 * @param l
		 * @param r
		 * @param f f(i) : 区間 i にクエリを投げる
		 */
		void apply(int l, int r, IntConsumer f) {
			if (!((0 <= l) && (l <= r) && (r <= n))) {
				throw new IllegalArgumentException("l=" + l + ", r=" + r + ", n=" + n);
			}
			for (int i : range(l, r)) {
				f.accept(i);
			}
		}
	}

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

	static interface IntTriConsumer {
		void accept(int a, int b, int c);
	}

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

		final int[] data;

		UnionFind(int n) {
			data = new int[n];
			Arrays.fill(data, -1);
		}

		int find(int k) {
			return (data[k] < 0) ? k : (data[k] = find(data[k]));
		}

		@SuppressWarnings("unused")
		boolean unite(int x, int y) {
			return unite(x, y, null);
		}

		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;
			if (null != f) {
				f.accept(x, y);
			}
			return true;
		}

		@SuppressWarnings("unused")
		int size(int k) {
			return -data[find(k)];
		}

		boolean same(int x, int y) {
			return find(x) == find(y);
		}
	}
}
0