結果
問題 | No.1170 Never Want to Walk |
ユーザー | neko_the_shadow |
提出日時 | 2020-08-24 12:46:54 |
言語 | Java21 (openjdk 21) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,057 bytes |
コンパイル時間 | 2,419 ms |
コンパイル使用メモリ | 88,368 KB |
実行使用メモリ | 102,896 KB |
最終ジャッジ日時 | 2024-04-24 03:25:53 |
合計ジャッジ時間 | 19,086 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
43,804 KB |
testcase_01 | AC | 64 ms
38,424 KB |
testcase_02 | AC | 66 ms
38,584 KB |
testcase_03 | AC | 67 ms
38,076 KB |
testcase_04 | AC | 65 ms
37,960 KB |
testcase_05 | AC | 69 ms
38,600 KB |
testcase_06 | AC | 65 ms
38,392 KB |
testcase_07 | AC | 65 ms
38,368 KB |
testcase_08 | AC | 66 ms
38,468 KB |
testcase_09 | AC | 65 ms
38,296 KB |
testcase_10 | AC | 65 ms
38,208 KB |
testcase_11 | AC | 67 ms
38,328 KB |
testcase_12 | AC | 152 ms
42,852 KB |
testcase_13 | AC | 156 ms
41,812 KB |
testcase_14 | AC | 157 ms
42,924 KB |
testcase_15 | AC | 157 ms
41,776 KB |
testcase_16 | AC | 153 ms
41,748 KB |
testcase_17 | AC | 153 ms
41,696 KB |
testcase_18 | AC | 157 ms
42,204 KB |
testcase_19 | AC | 154 ms
41,900 KB |
testcase_20 | AC | 151 ms
42,096 KB |
testcase_21 | AC | 157 ms
41,904 KB |
testcase_22 | AC | 287 ms
44,452 KB |
testcase_23 | AC | 227 ms
44,576 KB |
testcase_24 | AC | 268 ms
45,260 KB |
testcase_25 | AC | 272 ms
45,952 KB |
testcase_26 | AC | 251 ms
44,784 KB |
testcase_27 | AC | 1,605 ms
101,296 KB |
testcase_28 | AC | 1,478 ms
102,596 KB |
testcase_29 | AC | 1,578 ms
102,896 KB |
testcase_30 | AC | 1,478 ms
102,476 KB |
testcase_31 | AC | 1,473 ms
101,556 KB |
testcase_32 | TLE | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
ソースコード
package _1170; import java.io.BufferedReader; import java.io.EOFException; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.UncheckedIOException; import java.lang.reflect.Array; import java.lang.reflect.Field; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.TreeSet; import java.util.regex.Pattern; import java.util.stream.Collectors; import java.util.stream.IntStream; public class Main { public void exec() { int n = stdin.nextInt(); long a = stdin.nextLong(); long b = stdin.nextLong(); long[] x = stdin.nextLongArray(n); UnionFind uf = new UnionFind(n); Map<Long, Integer> toIndex = new HashMap<>(); for (int i = 0; i < n; i++) { toIndex.put(x[i], i); } TreeSet<Long> s1 = new TreeSet<>(); for (int i = n - 1; i >= 0; i--) { for (Long v : s1.subSet(a+x[i], b+x[i]+1)) { int j = toIndex.get(v); uf.union(i, j); } s1.add(x[i]); } TreeSet<Long> s2 = new TreeSet<>(); for (int i = 0; i < n; i++) { for (Long v : s2.subSet(x[i]-b, x[i]-a+1)) { int j = toIndex.get(v); uf.union(i, j); } s2.add(x[i]); } for (int i = 0; i < n; i++) { stdout.println(uf.size(i)); } } public class UnionFind { private int[] parent; private int[] size; public UnionFind(int n) { this.parent = IntStream.range(0, n).toArray(); this.size = new int[n]; Arrays.fill(this.size, 1); } public int find(int x) { if (parent[x] == x) { return x; } parent[x] = find(parent[x]); return parent[x]; } public boolean same(int x, int y) { return find(x) == find(y); } public void union(int x, int y) { x = find(x); y = find(y); if (x == y) { return ; } if (size[x] < size[y]) { parent[x] = y; size[y] += size[x]; } else { parent[y] = x; size[x] += size[y]; } } public int size(int x) { return size[find(x)]; } } private static final Stdin stdin = new Stdin(); private static final Stdout stdout = new Stdout(); public static void main(String[] args) { try { new Main().exec(); } finally { stdout.flush(); } } public static class Stdin { private BufferedReader stdin; private Deque<String> tokens; private Pattern delim; public Stdin() { stdin = new BufferedReader(new InputStreamReader(System.in)); tokens = new ArrayDeque<>(); delim = Pattern.compile(" "); } public String nextString() { try { if (tokens.isEmpty()) { String line = stdin.readLine(); if (line == null) { throw new UncheckedIOException(new EOFException()); } delim.splitAsStream(line).forEach(tokens::addLast); } return tokens.pollFirst(); } catch (IOException e) { throw new UncheckedIOException(e); } } public int nextInt() { return Integer.parseInt(nextString()); } public double nextDouble() { return Double.parseDouble(nextString()); } public long nextLong() { return Long.parseLong(nextString()); } public String[] nextStringArray(int n) { String[] a = new String[n]; for (int i = 0; i < n; i++) a[i] = nextString(); return a; } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } public static class Stdout { private PrintWriter stdout; public Stdout() { stdout = new PrintWriter(System.out, false); } public void printf(String format, Object ... args) { String line = String.format(format, args); if (line.endsWith(System.lineSeparator())) { stdout.print(line); } else { stdout.println(line); } } public void println(Object ... o) { String line = Arrays.stream(o).map(Objects::toString).collect(Collectors.joining(" ")); stdout.println(line); } public void debug(Object ... objs) { String line = Arrays.stream(objs).map(this::deepToString).collect(Collectors.joining(" ")); stdout.printf("DEBUG: %s%n", line); } private String deepToString(Object o) { if (o == null) { return "null"; } Class<?> clazz = o.getClass(); // 配列の場合 if (clazz.isArray()) { int len = Array.getLength(o); String[] tokens = new String[len]; for (int i = 0; i < len; i++) { tokens[i] = deepToString(Array.get(o, i)); } return "{" + String.join(",", tokens) + "}"; } // toStringがOverrideされている場合 if (Arrays.stream(clazz.getDeclaredMethods()).anyMatch(method -> method.getName().equals("toString") && method.getParameterCount() == 0)) { return Objects.toString(o); } // Tupleの場合 (フィールドがすべてpublicのJava Beans) try { List<String> tokens = new ArrayList<>(); for (Field field : clazz.getFields()) { String token = String.format("%s=%s", field.getName(), deepToString(field.get(o))); tokens.add(token); } return String.format("%s:[%s]", clazz.getName(), String.join(",", tokens)); } catch (IllegalAccessException e) { throw new IllegalArgumentException(e); } } public void flush() { stdout.flush(); } } }