結果
問題 | No.1234 典型RMQ |
ユーザー | shojin_pro |
提出日時 | 2020-10-12 20:48:11 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 826 ms / 2,000 ms |
コード長 | 5,178 bytes |
コンパイル時間 | 2,396 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 56,660 KB |
最終ジャッジ日時 | 2024-04-26 11:44:31 |
合計ジャッジ時間 | 18,958 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
37,344 KB |
testcase_01 | AC | 54 ms
37,248 KB |
testcase_02 | AC | 53 ms
37,164 KB |
testcase_03 | AC | 52 ms
36,936 KB |
testcase_04 | AC | 53 ms
36,956 KB |
testcase_05 | AC | 52 ms
37,164 KB |
testcase_06 | AC | 697 ms
52,040 KB |
testcase_07 | AC | 576 ms
48,100 KB |
testcase_08 | AC | 826 ms
56,412 KB |
testcase_09 | AC | 683 ms
50,832 KB |
testcase_10 | AC | 805 ms
54,212 KB |
testcase_11 | AC | 686 ms
53,672 KB |
testcase_12 | AC | 637 ms
50,276 KB |
testcase_13 | AC | 540 ms
48,300 KB |
testcase_14 | AC | 633 ms
50,312 KB |
testcase_15 | AC | 627 ms
50,100 KB |
testcase_16 | AC | 707 ms
54,992 KB |
testcase_17 | AC | 655 ms
50,200 KB |
testcase_18 | AC | 501 ms
48,252 KB |
testcase_19 | AC | 738 ms
54,040 KB |
testcase_20 | AC | 617 ms
51,964 KB |
testcase_21 | AC | 693 ms
54,640 KB |
testcase_22 | AC | 692 ms
55,904 KB |
testcase_23 | AC | 690 ms
56,660 KB |
testcase_24 | AC | 661 ms
56,536 KB |
testcase_25 | AC | 688 ms
55,736 KB |
testcase_26 | AC | 688 ms
55,792 KB |
testcase_27 | AC | 52 ms
37,156 KB |
testcase_28 | AC | 53 ms
37,312 KB |
testcase_29 | AC | 53 ms
37,344 KB |
ソースコード
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { FastScanner sc = new FastScanner(System.in); PrintWriter pw = new PrintWriter(System.out); int n = sc.nextInt(); LazySegmentTree st = new LazySegmentTree(n+1); for(int i = 0; i < n; i++){ st.update(i,i,sc.nextLong()); } int q = sc.nextInt(); for(int i = 0; i < q; i++){ int k = sc.nextInt(); int l = sc.nextInt()-1; int r = sc.nextInt()-1; long c = sc.nextLong(); if(k == 1){ st.update(l,r,c); }else{ pw.println(st.find(l,r)); } } pw.flush(); } static class GeekInteger { public static void save_sort(int[] array) { shuffle(array); Arrays.sort(array); } public static int[] shuffle(int[] array) { int n = array.length; Random random = new Random(); for (int i = 0, j; i < n; i++) { j = i + random.nextInt(n - i); int randomElement = array[j]; array[j] = array[i]; array[i] = randomElement; } return array; } } } class FastScanner { private BufferedReader reader = null; private StringTokenizer tokenizer = null; public FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } public String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } public double nextDouble() { return Double.parseDouble(next()); } public String[] nextArray(int n) { String[] a = new String[n]; for (int i = 0; i < n; i++) a[i] = next(); return a; } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } class LazySegmentTree{ long[] tree,lazy; boolean[] bool; int N; long INF = Long.MAX_VALUE/3; public LazySegmentTree(int n){ int now = 1; while(now < n){ now *= 2; } this.N = now; this.tree = new long[N*2]; this.lazy = new long[N*2]; this.bool = new boolean[N*2]; } public void eval(int k, int l, int r){ //更新分が残っている場合 if(bool[k]){ //自ノードの値配列に値を伝播させる tree[k] += lazy[k]; //子ノードの遅延配列に値を伝播させる + 最下層の時は終了する。 if(r-l > 1){ lazy[k*2+1] = lazy[k*2+2] = lazy[k]; bool[k*2+1] = bool[k*2+2] = true; } //更新完了したのでflgを戻す bool[k] = false; } } public void update(int a, int b, long x){ update(a,b+1,x,0,0,N); } public void update(int a, int b, long x, int k, int l, int r){ if(r < 0) r = N; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if(b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if(a <= l && r <= b) { lazy[k]+=x; tree[k]+=x; return; } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); tree[k] = lazy[k] + Math.min(tree[2*k+1], tree[2*k+2]); } return; } public long find(int a, int b){ return find(a,b+1,0,0,N); } public long find(int a, int b, int k, int l, int r) { if(r < 0) r = N; eval(k, l, r); if(b <= l || r <= a) return INF; if(a <= l && r <= b) return tree[k]; long vl = find(a, b, 2*k+1, l, (l+r)/2); long vr = find(a, b, 2*k+2, (l+r)/2, r); return lazy[k] + Math.min(vl, vr); } }