結果
| 問題 |
No.878 Range High-Element Query
|
| コンテスト | |
| ユーザー |
 kusomushi
|
| 提出日時 | 2019-09-08 21:49:36 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 796 ms / 2,000 ms |
| コード長 | 7,360 bytes |
| コンパイル時間 | 2,744 ms |
| コンパイル使用メモリ | 81,232 KB |
| 実行使用メモリ | 76,884 KB |
| 最終ジャッジ日時 | 2024-06-27 15:16:26 |
| 合計ジャッジ時間 | 10,723 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 18 |
ソースコード
import java.io.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.function.Function;
import java.util.function.LongPredicate;
public class Main {
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
int N = sc.nextInt();
int Q = sc.nextInt();
int[] A = sc.nextIntArray(N, -1);
int log = Integer.toBinaryString(N-1).length(); // 最大でN-1
int[][] next = new int[log][N+1];
for (int i = 0; i < log; i++) {
next[i][N] = N;
}
int[] rev = new int[N];
for (int i = 0; i < N; i++) {
rev[A[i]] = i;
}
TreeSet<Integer> indice = new TreeSet<>();
indice.add(N);
for (int a = N-1; a >= 0; a--) {
int i = rev[a];
next[0][i] = indice.higher(i);
indice.add(i);
}
for (int i = 1; i < log; i++) {
for (int j = 0; j < N; j++) {
// j -> next[i-1]
next[i][j] = next[i-1][next[i-1][j]];
}
}
PrintWriter pw = new PrintWriter(System.out);
for (int q = 0; q < Q; q++) {
int type = sc.nextInt(); // 使わない
int l = sc.nextInt()-1;
int r = sc.nextInt()-1;
// [l, r]
int time = 0;
int curr = l;
lo:
while(curr < r) {
for (int i = log-1; i >= 0; i--) {
int ne = next[i][curr];
if( ne <= r ) {
curr = ne;
time += 1 << i;
continue lo;
}
}
break;
}
pw.println(time+1);
}
pw.flush();
}
static class RangeGet {
interface Monoid {
long identity();
long apply(long a, long b);
}
static Monoid MOD_SUM(int mod) {
return new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) {
long c = a + b;
if( c >= mod ) {
c %= mod;
}
return c;
}
};
}
static Monoid SUM = new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) { return a + b; }
};
static Monoid MAX = new Monoid() {
public long identity() { return Long.MIN_VALUE / 2; }
public long apply(long a, long b) { return Math.max(a, b); }
};
static Monoid MIN = new Monoid() {
public long identity() { return Long.MAX_VALUE / 2; }
public long apply(long a, long b) { return Math.min(a, b); }
};
int size;
long[] tree;
Monoid m;
long identity;
RangeGet(int size, Monoid m) {
this.size = 1;
while( this.size < size ) this.size *= 2;
this.tree = new long[this.size*2];
this.m = m;
this.identity = m.identity();
if( this.identity != 0 ) {
Arrays.fill(this.tree, this.identity);
}
}
void update(int idx, long v) {
idx += size;
tree[idx] = v;
while(idx > 0) {
idx /= 2;
tree[idx] = m.apply(tree[idx*2], tree[idx*2+1]);
}
}
// [from, to)
long query(int from, int to) {
return _query(from, to, 1, 0, size);
}
long _query(int from, int to, int idx, int l, int r) {
if (r <= from || to <= l) return identity;
if (from <= l && r <= to) {
return tree[idx];
} else {
int mid = (l+r)/2;
long vl = _query(from, to, idx*2, l, mid);
long vr = _query(from, to, idx*2+1, mid, r);
return m.apply(vl, vr);
}
}
long get(int idx) {
return tree[idx+size];
}
}
@SuppressWarnings("unused")
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
long nextLong() {
return Long.parseLong(next());
}
int nextInt() {
return Integer.parseInt(next());
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
int[] nextIntArray(int n, int delta) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt() + delta;
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
}
static <A> void writeLines(A[] as, Function<A, String> f) {
PrintWriter pw = new PrintWriter(System.out);
for (A a : as) {
pw.println(f.apply(a));
}
pw.flush();
}
static void writeLines(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int a : as) pw.println(a);
pw.flush();
}
static void writeLines(long[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (long a : as) pw.println(a);
pw.flush();
}
static int max(int... as) {
int max = Integer.MIN_VALUE;
for (int a : as) max = Math.max(a, max);
return max;
}
static int min(int... as) {
int min = Integer.MAX_VALUE;
for (int a : as) min = Math.min(a, min);
return min;
}
static void debug(Object... args) {
StringJoiner j = new StringJoiner(" ");
for (Object arg : args) {
if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
else j.add(arg.toString());
}
System.err.println(j.toString());
}
}