Submit Info #2595

Problem Lang User Status Time Memory
Static RMQ java mikit AC 1768 ms 418.29 MiB

ケース詳細
Name Status Time Memory
example_00 AC 91 ms 10.23 MiB
max_random_00 AC 1768 ms 411.16 MiB
max_random_01 AC 1671 ms 415.30 MiB
max_random_02 AC 1757 ms 410.95 MiB
max_random_03 AC 1701 ms 418.29 MiB
max_random_04 AC 1720 ms 415.32 MiB
random_00 AC 1539 ms 321.75 MiB
random_01 AC 1647 ms 395.86 MiB
random_02 AC 805 ms 117.92 MiB
random_03 AC 930 ms 252.27 MiB
random_04 AC 1037 ms 229.22 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.lang.reflect.Array; import java.util.function.BiFunction; import java.io.BufferedOutputStream; import java.nio.charset.Charset; import java.util.StringTokenizer; import java.io.OutputStreamWriter; import java.io.OutputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.function.BinaryOperator; import java.io.UncheckedIOException; import java.util.Objects; import java.io.Writer; import java.io.BufferedReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top * * @author mikit */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; LightScanner in = new LightScanner(inputStream); LightWriter out = new LightWriter(outputStream); V solver = new V(); solver.solve(1, in, out); out.close(); } static class V { public void solve(int testNumber, LightScanner in, LightWriter out) { int n = in.ints(), q = in.ints(); Long[] a = new Long[n]; for (int i = 0; i < n; i++) a[i] = in.longs(); SparseTable<Long> st = new SparseTable<>(a, Math::min); for (int i = 0; i < q; i++) out.ans(st.query(in.ints(), in.ints())).ln(); } } static class LightWriter implements AutoCloseable { private final Writer out; private boolean autoflush = false; private boolean breaked = true; public LightWriter(Writer out) { this.out = out; } public LightWriter(OutputStream out) { this(new OutputStreamWriter(new BufferedOutputStream(out), Charset.defaultCharset())); } public LightWriter print(char c) { try { out.write(c); breaked = false; } catch (IOException ex) { throw new UncheckedIOException(ex); } return this; } public LightWriter print(String s) { try { out.write(s, 0, s.length()); breaked = false; } catch (IOException ex) { throw new UncheckedIOException(ex); } return this; } public LightWriter ans(String s) { if (!breaked) { print(' '); } return print(s); } public LightWriter ans(Object obj) { return ans(Objects.toString(obj)); } public LightWriter ln() { print(System.lineSeparator()); breaked = true; if (autoflush) { try { out.flush(); } catch (IOException ex) { throw new UncheckedIOException(ex); } } return this; } public void close() { try { out.close(); } catch (IOException ex) { throw new UncheckedIOException(ex); } } } static class Reflection { public static <T> Class<? extends T> getComponentClass(T[] a) { return (Class<? extends T>) a.getClass().getComponentType(); } public static <T> Class<? extends T> getClass(T t) { return (Class<? extends T>) t.getClass(); } public static <T> T[] newInstance(Class<T> clazz, int length) { return (T[]) Array.newInstance(clazz, length); } } static class SparseTable<T> { private final int n; private final BinaryOperator<T> f; private final T[][] table; public SparseTable(T[] a, BinaryOperator<T> f) { this.n = a.length; this.f = f; this.table = Reflection.newInstance(Reflection.getClass(a), 30); table[0] = a.clone(); for (int i = 1; (1 << i) < n; i++) { table[i] = Reflection.newInstance(Reflection.getComponentClass(a), n); int r = 1 << i, d = r + r; for (int j = r - 1; j < n; j += d) { table[i][j] = a[j]; for (int k = 1; k < r; k++) table[i][j - k] = f.apply(a[j - k], table[i][j - k + 1]); } for (int j = r; j < n; j += d) { table[i][j] = a[j]; for (int k = j + 1; k < j + r && k < n; k++) table[i][k] = f.apply(a[k], table[i][k - 1]); } } } public T query(int l, int r) { if (r <= l || l < 0 || n < r) throw new RuntimeException(); if (l == --r) return table[0][l]; int k = BitMath.msb(l ^ r); return f.apply(table[k][l], table[k][r]); } } static final class BitMath { private BitMath() { } public static int count(int v) { v = (v & 0x55555555) + ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f); v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff); v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff); return v; } public static int msb(int v) { if (v == 0) { throw new IllegalArgumentException("Bit not found"); } v |= (v >> 1); v |= (v >> 2); v |= (v >> 4); v |= (v >> 8); v |= (v >> 16); return count(v) - 1; } } static class LightScanner { private BufferedReader reader = null; private StringTokenizer tokenizer = null; public LightScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); } public String string() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new UncheckedIOException(e); } } return tokenizer.nextToken(); } public int ints() { return Integer.parseInt(string()); } public long longs() { return Long.parseLong(string()); } } }