Submit Info #66678

Problem Lang User Status Time Memory
Associative Array java dalt AC 1343 ms 205.36 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 1343 ms 205.36 MiB
example_00 AC 72 ms 10.57 MiB
many_0set_00 AC 1133 ms 138.18 MiB
many_0set_sparse_00 AC 381 ms 36.46 MiB
max_random_00 AC 1195 ms 139.96 MiB
max_random_01 AC 1078 ms 139.11 MiB
max_random_02 AC 1108 ms 142.20 MiB
random_00 AC 606 ms 58.04 MiB
random_01 AC 665 ms 66.10 MiB
random_02 AC 850 ms 135.23 MiB
sparse_keys_00 AC 381 ms 38.04 MiB
sparse_keys_01 AC 365 ms 41.69 MiB
unordered_map_killer_00 AC 944 ms 129.92 MiB
unordered_map_killer_01 AC 1235 ms 199.53 MiB
unordered_map_killer_02 AC 1173 ms 200.19 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.util.stream.IntStream; import java.util.Arrays; import java.util.Random; import java.util.HashMap; import java.util.Map; import java.util.NoSuchElementException; import java.io.OutputStream; import java.util.Iterator; import java.io.IOException; import java.lang.reflect.Field; import java.nio.charset.StandardCharsets; import java.io.UncheckedIOException; import java.util.stream.Stream; import java.io.Closeable; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); AssociativeArray solver = new AssociativeArray(); solver.solve(1, in, out); out.close(); } } static class AssociativeArray { public void solve(int testNumber, FastInput in, FastOutput out) { int q = in.ri(); long[][] qs = new long[q][]; long[] keys = new long[q]; for (int i = 0; i < q; i++) { long t = in.rl(); long k = in.rl(); keys[i] = k; if (t == 0) { qs[i] = new long[]{k, in.rl()}; } else { qs[i] = new long[]{k}; } } SortUtils.radixSort(keys, 0, q - 1); keys = SortUtils.unique(keys, 0, q - 1, LongComparator.NATURE_ORDER); long[] V = new long[keys.length]; Integer[] indices = IntStream.range(0, keys.length).boxed().toArray(x -> new Integer[x]); PerfectHashing<Integer> ph = new PerfectHashing<>(keys, indices); for (long[] query : qs) { if (query.length == 1) { out.println(V[ph.get(query[0])]); } else { V[ph.get(query[0])] = query[1]; } } } } static class PerfectHashing<V> implements Iterable<V> { HashFunction f1 = FastUniversalHashFunction0.getInstance(); HashFunction[] f2; long notExistKey; int[] starts; int[] masks; long[] K; Object[] V; int globalMask; private PerfectHashing(int m) { m = 1 << Log2.ceilLog(m); globalMask = m - 1; starts = new int[m]; masks = new int[m]; f2 = new HashFunction[m]; for (int i = 0; i < m; i++) { f2[i] = FastUniversalHashFunction0.getInstance(); } } public PerfectHashing(long[] keys, V[] values) { this((int) Math.ceil(keys.length)); while (true) { notExistKey = RandomWrapper.INSTANCE.nextLong(); boolean find = false; for (long k : keys) { if (k == notExistKey) { find = true; break; } } if (!find) { break; } } init0(keys, values, new int[keys.length]); } private void init0(long[] keys, V[] values, int[] h1) { int n = keys.length; Arrays.fill(masks, 0); for (int i = 0; i < n; i++) { long k = keys[i]; masks[h1[i] = ((int) f1.f(k) & globalMask)]++; } long total = 0; for (int i = 0; i < n; i++) { total += (1L << Log2.ceilLog((long) masks[i] * masks[i])); } //success hash if (total >= 5 * starts.length) { f1 = f1.upgrade(); init0(keys, values, h1); return; } for (int i = 0; i < masks.length; i++) { starts[i] = masks[i]; if (i > 0) { starts[i] += starts[i - 1]; } } int[] indices = new int[n]; for (int i = 0; i < n; i++) { indices[--starts[h1[i]]] = i; } total = 0; for (int i = 0; i < starts.length; i++) { starts[i] = (int) total; masks[i] = (int) ((1L << Log2.ceilLog((long) masks[i] * masks[i])) - 1); total += masks[i] + 1; } K = new long[(int) total]; V = new Object[(int) total]; for (int i = 0; i < n; i++) { int l = i; int r = l; int h = h1[indices[l]]; int L = starts[h]; int M = masks[h]; while (r + 1 < n && h == h1[indices[r + 1]]) { r++; } i = r; while (true) { Arrays.fill(K, L, L + M + 1, notExistKey); boolean success = true; HashFunction f = f2[h]; for (int j = l; j <= r; j++) { int index = indices[j]; int h2 = L + ((int) f.f(keys[index]) & M); if (K[h2] != notExistKey) { success = false; break; } V[h2] = values[index]; K[h2] = keys[index]; } if (success) { break; } f2[h] = f2[h].upgrade(); } } } public Iterator<V> iterator() { return new Iterator<V>() { int cur = 0; public boolean hasNext() { while (cur <= globalMask && K[cur] == notExistKey) { cur++; } return cur <= globalMask; } public V next() { if (!hasNext()) { throw new NoSuchElementException(); } return (V) V[cur]; } }; } public V getOrDefault(long key, V def) { // int h1 = (int) f1.f(key) & globalMask; // if (masks[h1] <= THRESHOLD) { // int l = starts[h1]; // int r = l + masks[h1]; // while (l <= r) { // if (K[l] != key || key == notExistKey) { // l++; // } else { // return (V) V[l]; // } // } // return def; // } // int h2 = ((int) f2[h1].f(key) & masks[h1]); // int index = starts[h1] + h2; // return K[index] != key || key == notExistKey ? def : (V) V[index]; int h1 = (int) f1.f(key) & globalMask; int h2 = masks[h1] == 0 ? 0 : ((int) f2[h1].f(key) & masks[h1]); int index = starts[h1] + h2; return K[index] != key || key == notExistKey ? def : (V) V[index]; } public V get(long key) { return getOrDefault(key, null); } public String toString() { Map<Long, V> map = new HashMap<>(); for (int i = 0; i < K.length; i++) { if (K[i] == notExistKey) { continue; } map.put(K[i], (V) V[i]); } return map.toString(); } } static class UniversalHashFunction implements HashFunction { public static int numberOfInstance = 0; private static ILongModular modular = LongModular2305843009213693951.getInstance(); private static long mod = modular.getMod(); long a; long b; { numberOfInstance++; upgrade(); } public long f(long x) { long ans = modular.mul(x, a); ans += b; if (ans >= mod) { ans -= mod; } return ans; } public HashFunction upgrade() { this.a = RandomWrapper.INSTANCE.nextLong(1, mod - 1); this.b = RandomWrapper.INSTANCE.nextLong(0, mod - 1); return this; } } static class FastUniversalHashFunction4 implements HashFunction { static final FastUniversalHashFunction4 INSTANCE = new FastUniversalHashFunction4(); private FastUniversalHashFunction4() { } public long f(long x) { long ans = x * 2654435761L; return ans ^ (ans >>> 32); } public HashFunction upgrade() { // return FastUniversalHashFunction5.INSTANCE; FastUniversalHashFunction0.numberOfInstance--; return new UniversalHashFunction(); } } static class FastUniversalHashFunction0 implements HashFunction { public static long numberOfInstance = 0; static final FastUniversalHashFunction0 INSTANCE = new FastUniversalHashFunction0(); public static FastUniversalHashFunction0 getInstance() { numberOfInstance++; return INSTANCE; } private FastUniversalHashFunction0() { } public long f(long x) { return x ^ (x >>> 32); } public HashFunction upgrade() { return FastUniversalHashFunction4.INSTANCE; // FastUniversalHashFunction0.numberOfInstance--; // return new UniversalHashFunction(); } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int ri() { return readInt(); } public int readInt() { boolean rev = false; skipBlank(); if (next == '+' || next == '-') { rev = next == '-'; next = read(); } int val = 0; while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } return rev ? val : -val; } public long rl() { return readLong(); } public long readLong() { boolean rev = false; skipBlank(); if (next == '+' || next == '-') { rev = next == '-'; next = read(); } long val = 0; while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } return rev ? val : -val; } } static interface HashFunction { long f(long x); HashFunction upgrade(); } static class SortUtils { private static final int THRESHOLD = 8; private static final int[] BUF8 = new int[1 << 8]; private static final LongArrayList LONG_LIST_A = new LongArrayList(); private SortUtils() { } public static void insertSort(long[] data, LongComparator cmp, int l, int r) { for (int i = l + 1; i <= r; i++) { int j = i; long val = data[i]; while (j > l && cmp.compare(data[j - 1], val) > 0) { data[j] = data[j - 1]; j--; } data[j] = val; } } public static void quickSort(long[] data, LongComparator cmp, int f, int t) { if (t - f <= THRESHOLD) { insertSort(data, cmp, f, t - 1); return; } SequenceUtils.swap(data, f, RandomWrapper.INSTANCE.nextInt(f, t - 1)); int l = f; int r = t; int m = l + 1; while (m < r) { int c = cmp.compare(data[m], data[l]); if (c == 0) { m++; } else if (c < 0) { SequenceUtils.swap(data, l, m); l++; m++; } else { SequenceUtils.swap(data, m, --r); } } quickSort(data, cmp, f, l); quickSort(data, cmp, m, t); } public static void radixSort(long[] data, int l, int r) { LONG_LIST_A.clear(); LONG_LIST_A.ensureSpace(r - l + 1); int n = r - l + 1; for (int i = 0; i < 8; i += 2) { radixSort0(data, l, r, LONG_LIST_A.getData(), 0, BUF8, i * 8); radixSort0(LONG_LIST_A.getData(), 0, n - 1, data, l, BUF8, (i + 1) * 8); } } private static void radixSort0(long[] data, int dl, int dr, long[] output, int ol, int[] buf, int rightShift) { Arrays.fill(buf, 0); int mask = buf.length - 1; for (int i = dl; i <= dr; i++) { buf[(int) ((data[i] >>> rightShift) & mask)]++; } for (int i = 1; i < buf.length; i++) { buf[i] += buf[i - 1]; } for (int i = dr; i >= dl; i--) { output[ol + (--buf[(int) ((data[i] >>> rightShift) & mask)])] = data[i]; } } public static <T> long[] unique(long[] data, int l, int r, LongComparator comp) { quickSort(data, comp, l, r + 1); int wpos = l + 1; for (int i = l + 1; i <= r; i++) { if (comp.compare(data[i], data[i - 1]) == 0) { continue; } else { data[wpos++] = data[i]; } } return Arrays.copyOfRange(data, l, wpos); } } static interface ILongModular { long getMod(); long mul(long a, long b); } static class FastOutput implements AutoCloseable, Closeable, Appendable { private static final int THRESHOLD = 32 << 10; private OutputStream writer; private StringBuilder cache = new StringBuilder(THRESHOLD * 2); private static Field stringBuilderValueField; private char[] charBuf = new char[THRESHOLD * 2]; private byte[] byteBuf = new byte[THRESHOLD * 2]; static { try { stringBuilderValueField = StringBuilder.class.getSuperclass().getDeclaredField("value"); stringBuilderValueField.setAccessible(true); } catch (Exception e) { stringBuilderValueField = null; } stringBuilderValueField = null; } public FastOutput append(CharSequence csq) { cache.append(csq); return this; } public FastOutput append(CharSequence csq, int start, int end) { cache.append(csq, start, end); return this; } private void afterWrite() { if (cache.length() < THRESHOLD) { return; } flush(); } public FastOutput(OutputStream writer) { this.writer = writer; } public FastOutput append(char c) { cache.append(c); afterWrite(); return this; } public FastOutput append(long c) { cache.append(c); afterWrite(); return this; } public FastOutput println(long c) { return append(c).println(); } public FastOutput println() { return append('\n'); } public FastOutput flush() { try { if (stringBuilderValueField != null) { try { byte[] value = (byte[]) stringBuilderValueField.get(cache); writer.write(value, 0, cache.length()); } catch (Exception e) { stringBuilderValueField = null; } } if (stringBuilderValueField == null) { int n = cache.length(); if (n > byteBuf.length) { //slow writer.write(cache.toString().getBytes(StandardCharsets.UTF_8)); // writer.append(cache); } else { cache.getChars(0, n, charBuf, 0); for (int i = 0; i < n; i++) { byteBuf[i] = (byte) charBuf[i]; } writer.write(byteBuf, 0, n); } } writer.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { writer.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } static class LongArrayList implements Cloneable { private int size; private int cap; private long[] data; private static final long[] EMPTY = new long[0]; public long[] getData() { return data; } public LongArrayList(int cap) { this.cap = cap; if (cap == 0) { data = EMPTY; } else { data = new long[cap]; } } public LongArrayList(long[] data) { this(0); addAll(data); } public LongArrayList(LongArrayList list) { this.size = list.size; this.cap = list.cap; this.data = Arrays.copyOf(list.data, size); } public LongArrayList() { this(0); } public void ensureSpace(int req) { if (req > cap) { while (cap < req) { cap = Math.max(cap + 10, 2 * cap); } data = Arrays.copyOf(data, cap); } } public void addAll(long[] x) { addAll(x, 0, x.length); } public void addAll(long[] x, int offset, int len) { ensureSpace(size + len); System.arraycopy(x, offset, data, size, len); size += len; } public void addAll(LongArrayList list) { addAll(list.data, 0, list.size); } public long[] toArray() { return Arrays.copyOf(data, size); } public void clear() { size = 0; } public String toString() { return Arrays.toString(toArray()); } public boolean equals(Object obj) { if (!(obj instanceof LongArrayList)) { return false; } LongArrayList other = (LongArrayList) obj; return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1); } public int hashCode() { int h = 1; for (int i = 0; i < size; i++) { h = h * 31 + Long.hashCode(data[i]); } return h; } public LongArrayList clone() { LongArrayList ans = new LongArrayList(); ans.addAll(this); return ans; } } static class SequenceUtils { public static void swap(long[] data, int i, int j) { long tmp = data[i]; data[i] = data[j]; data[j] = tmp; } public static boolean equal(long[] a, int al, int ar, long[] b, int bl, int br) { if ((ar - al) != (br - bl)) { return false; } for (int i = al, j = bl; i <= ar; i++, j++) { if (a[i] != b[j]) { return false; } } return true; } } static interface LongComparator { public static final LongComparator NATURE_ORDER = (a, b) -> Long.compare(a, b); public int compare(long a, long b); } static class LongModular2305843009213693951 implements ILongModular { private static long mod = 2305843009213693951L; private static final LongModular2305843009213693951 INSTANCE = new LongModular2305843009213693951(); private static long mask = (1L << 32) - 1; private LongModular2305843009213693951() { } public static final LongModular2305843009213693951 getInstance() { return INSTANCE; } public long getMod() { return mod; } public long mul(long a, long b) { long l1 = a & mask; long h1 = (a >> 32) & mask; long l2 = b & mask; long h2 = (b >> 32) & mask; long l = l1 * l2; long m = l1 * h2 + l2 * h1; long h = h1 * h2; long ret = (l & mod) + (l >>> 61) + (h << 3) + (m >>> 29) + ((m << 35) >>> 3) + 1; ret = (ret & mod) + (ret >>> 61); ret = (ret & mod) + (ret >>> 61); return ret - 1; } } static class Log2 { public static int ceilLog(int x) { if (x <= 0) { return 0; } return 32 - Integer.numberOfLeadingZeros(x - 1); } public static int ceilLog(long x) { if (x <= 0) { return 0; } return 64 - Long.numberOfLeadingZeros(x - 1); } } static class RandomWrapper { private Random random; public static final RandomWrapper INSTANCE = new RandomWrapper(); public RandomWrapper() { this(new Random()); } public RandomWrapper(Random random) { this.random = random; } public RandomWrapper(long seed) { this(new Random(seed)); } public int nextInt(int l, int r) { return random.nextInt(r - l + 1) + l; } public long nextLong(long l, long r) { return nextLong(r - l + 1) + l; } public long nextLong(long n) { return Math.round(random.nextDouble() * (n - 1)); } public long nextLong() { return random.nextLong(); } } }