結果
問題 | No.875 Range Mindex Query |
ユーザー | ks2m |
提出日時 | 2019-10-25 00:34:04 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 650 ms / 2,000 ms |
コード長 | 2,342 bytes |
コンパイル時間 | 2,039 ms |
コンパイル使用メモリ | 73,912 KB |
実行使用メモリ | 67,092 KB |
最終ジャッジ日時 | 2023-09-25 11:20:15 |
合計ジャッジ時間 | 9,657 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
49,704 KB |
testcase_01 | AC | 83 ms
51,668 KB |
testcase_02 | AC | 82 ms
51,820 KB |
testcase_03 | AC | 53 ms
49,564 KB |
testcase_04 | AC | 62 ms
50,500 KB |
testcase_05 | AC | 58 ms
49,880 KB |
testcase_06 | AC | 66 ms
50,776 KB |
testcase_07 | AC | 78 ms
51,980 KB |
testcase_08 | AC | 63 ms
50,416 KB |
testcase_09 | AC | 60 ms
50,508 KB |
testcase_10 | AC | 89 ms
51,736 KB |
testcase_11 | AC | 603 ms
62,848 KB |
testcase_12 | AC | 523 ms
62,372 KB |
testcase_13 | AC | 495 ms
65,500 KB |
testcase_14 | AC | 499 ms
64,776 KB |
testcase_15 | AC | 628 ms
66,412 KB |
testcase_16 | AC | 627 ms
66,804 KB |
testcase_17 | AC | 650 ms
67,092 KB |
testcase_18 | AC | 621 ms
67,012 KB |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int q = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } SegmentTree st = new SegmentTree(n); st.init(a); PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); int p = Integer.parseInt(sa[0]); int l = Integer.parseInt(sa[1]) - 1; int r = Integer.parseInt(sa[2]); if (p == 1) { r--; st.update(l, r); } else { pw.println(st.query(l, r, 0, 0, st.n).i + 1); } } pw.flush(); } static class SegmentTree { int n = 2; int n2; Obj[] arr; Obj INF = new Obj(-1, Integer.MAX_VALUE); public SegmentTree(int x) { while (n < x) { n <<= 1; } n2 = n * 2 - 1; arr = new Obj[n2]; } void init(int[] a) { for (int i = 0; i < a.length; i++) { arr[i + n - 1] = new Obj(i, a[i]); } for (int i = a.length + n - 1; i < n2; i++) { arr[i] = INF; } for (int i = n - 2; i >= 0; i--) { if (arr[i * 2 + 1].a < arr[i * 2 + 2].a) { arr[i] = arr[i * 2 + 1]; } else { arr[i] = arr[i * 2 + 2]; } } } void update(int l, int r) { l += n - 1; r += n - 1; int a = arr[l].a; arr[l].a = arr[r].a; arr[r].a = a; update2(l); update2(r); } void update2(int i) { while (i > 0) { i = (i - 1) / 2; if (arr[i * 2 + 1].a < arr[i * 2 + 2].a) { arr[i] = arr[i * 2 + 1]; } else { arr[i] = arr[i * 2 + 2]; } } } Obj query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return INF; // 交差しない if (a <= l && r <= b) return arr[k]; // 完全に含む Obj o1 = query(a, b, k * 2 + 1, l, (l + r) / 2); Obj o2 = query(a, b, k * 2 + 2, (l + r) / 2, r); if (o1.a < o2.a) { return o1; } return o2; } static class Obj { int i, a; public Obj(int i, int a) { this.i = i; this.a = a; } public String toString() { return String.valueOf(a); } } } }