Submit Info #2596

Problem Lang User Status Time Memory
Static RMQ java mikit AC 979 ms 180.07 MiB

ケース詳細
Name Status Time Memory
example_00 AC 128 ms 10.52 MiB
max_random_00 AC 887 ms 179.53 MiB
max_random_01 AC 893 ms 179.44 MiB
max_random_02 AC 888 ms 179.30 MiB
max_random_03 AC 979 ms 180.07 MiB
max_random_04 AC 909 ms 178.69 MiB
random_00 AC 810 ms 156.60 MiB
random_01 AC 872 ms 171.37 MiB
random_02 AC 663 ms 101.39 MiB
random_03 AC 550 ms 104.01 MiB
random_04 AC 621 ms 122.69 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.util.stream.IntStream; import java.util.stream.LongStream; import java.util.function.LongBinaryOperator; import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedOutputStream; import java.io.UncheckedIOException; import java.nio.charset.Charset; import java.util.StringTokenizer; import java.io.Writer; import java.io.OutputStreamWriter; 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(); IntSparseTable st = new IntSparseTable(in.longs(n), 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(long l) { return ans(Long.toString(l)); } 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 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()); } public long[] longs(int length) { return IntStream.range(0, length).mapToLong(x -> longs()).toArray(); } } static class IntSparseTable { private final int n; private final LongBinaryOperator f; private final long[][] table; public IntSparseTable(long[] a, LongBinaryOperator f) { this.n = a.length; this.f = f; this.table = new long[30][]; table[0] = a.clone(); for (int i = 1; (1 << i) < n; i++) { table[i] = new long[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.applyAsLong(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.applyAsLong(a[k], table[i][k - 1]); } } } public long 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.applyAsLong(table[k][l], table[k][r]); } } }