結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | uwi |
提出日時 | 2018-12-23 00:21:47 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,541 ms / 3,000 ms |
コード長 | 10,243 bytes |
コンパイル時間 | 4,539 ms |
コンパイル使用メモリ | 89,704 KB |
実行使用メモリ | 101,760 KB |
最終ジャッジ日時 | 2024-09-25 10:20:41 |
合計ジャッジ時間 | 32,387 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
37,004 KB |
testcase_01 | AC | 54 ms
37,140 KB |
testcase_02 | AC | 291 ms
49,488 KB |
testcase_03 | AC | 709 ms
83,696 KB |
testcase_04 | AC | 592 ms
52,044 KB |
testcase_05 | AC | 1,174 ms
93,184 KB |
testcase_06 | AC | 479 ms
58,132 KB |
testcase_07 | AC | 858 ms
90,184 KB |
testcase_08 | AC | 846 ms
73,872 KB |
testcase_09 | AC | 530 ms
72,936 KB |
testcase_10 | AC | 531 ms
58,256 KB |
testcase_11 | AC | 999 ms
101,760 KB |
testcase_12 | AC | 1,171 ms
93,100 KB |
testcase_13 | AC | 1,194 ms
92,984 KB |
testcase_14 | AC | 1,243 ms
93,092 KB |
testcase_15 | AC | 1,192 ms
93,056 KB |
testcase_16 | AC | 1,218 ms
92,928 KB |
testcase_17 | AC | 1,541 ms
93,840 KB |
testcase_18 | AC | 1,058 ms
92,892 KB |
testcase_19 | AC | 1,188 ms
91,220 KB |
testcase_20 | AC | 1,250 ms
93,604 KB |
testcase_21 | AC | 1,190 ms
91,724 KB |
testcase_22 | AC | 1,228 ms
93,468 KB |
testcase_23 | AC | 1,236 ms
93,868 KB |
testcase_24 | AC | 1,217 ms
93,640 KB |
testcase_25 | AC | 241 ms
44,024 KB |
testcase_26 | AC | 1,034 ms
94,868 KB |
testcase_27 | AC | 987 ms
90,844 KB |
ソースコード
package adv2018; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Day24 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(), Q = ni(); int[] a = na(n); StarrySkyTreeL prefix = new StarrySkyTreeL(n); StarrySkyTreeL suffix = new StarrySkyTreeL(n); SegmentTreeSeqMaxSum st = new SegmentTreeSeqMaxSum(n); for(int i = 0;i < n;i++){ prefix.add(i, n, -a[i]); suffix.add(0, i+1, -a[i]); st.update(i, a[i]); } for(int z = 0;z < Q;z++){ char type = ns().charAt(0); if(type == 's'){ int pos = ni()-1; int x = ni(); int d = x - a[pos]; a[pos] = x; prefix.add(pos, n, -d); suffix.add(0, pos+1, -d); st.update(pos, a[pos]); }else{ int l1 = ni()-1; int l2 = ni()-1; int r1 = ni()-1; int r2 = ni()-1; if(r1 < l1){ r1 = l1; } if(r2 < l2){ l2 = r2; } long ans = Long.MIN_VALUE; { int l3 = Math.min(l2, r1); long v = -(suffix.minx(l1, l3+1) - suffix.minx(l3+1, l3+2)) + -(prefix.minx(r1, r2+1) - prefix.minx(l3, l3+1)); ans = Math.max(ans, v); } { int r0 = Math.max(l2, r1); // [l1,l2],[r0,r2] long v = -(suffix.minx(l1, l2+1) - suffix.minx(l2+1, l2+2)) + -(prefix.minx(r0, r2+1) - prefix.minx(l2, l2+1)); ans = Math.max(ans, v); } if(l2 >= r1){ long v = st.smax(r1, l2+1)[3]; ans = Math.max(ans, v); } out.println(ans); } } } public static class SegmentTreeSeqMaxSum { public int M, H, N; public long[][] st; // [全体の和, 左側の和の最大値, 右側の和の最大値, 中の和の最大値] どれも1個以上 public long I = Long.MIN_VALUE/2 + 30000; public SegmentTreeSeqMaxSum(int[] a) { N = a.length; M = Integer.highestOneBit(Math.max(N-1, 1))<<2; H = M>>>1; st = new long[M][4]; for(int i = 0;i < H;i++){ long v = i < N ? a[i] : I; Arrays.fill(st[H+i], v); } for(int i = H-1;i >= 1;i--){ propagate(i); } } public SegmentTreeSeqMaxSum(int n) { N = n; M = Integer.highestOneBit(Math.max(N-1, 1))<<2; H = M>>>1; st = new long[M][4]; for(int i = 0;i < H;i++){ Arrays.fill(st[H+i], I); } for(int i = H-1;i >= 1;i--){ propagate(i); } } private void propagate(int i) { long[] P = st[i], L = st[2*i], R = st[2*i+1]; propNC(P, L, R); } private long[] propNC(long[] P, long[] L, long[] R) { P[0] = Math.max(L[0] + R[0], I); P[1] = Math.max(L[1], L[0]+R[1]); P[2] = Math.max(R[2], L[2]+R[0]); P[3] = Math.max(Math.max(L[3], R[3]), Math.max(L[2], Math.max(L[2]+R[1], R[1]))); return P; } public void update(int pos, long v) { Arrays.fill(st[H+pos], v); for(int x = H+pos>>>1;x != 0;x>>>=1){ propNC(st[x], st[2*x], st[2*x+1]); } } public long[] smax(int l, int r){ return smax(l, r, 0, H, 1); } private long[] smax(int l, int r, int cl, int cr, int cur) { if(l <= cl && cr <= r){ return Arrays.copyOf(st[cur], st[cur].length); }else{ int mid = cl+cr>>>1; long[] L = null, R = null; if(cl < r && l < mid){ L = smax(l, r, cl, mid, 2*cur); } if(mid < r && l < cr){ R = smax(l, r, mid, cr, 2*cur+1); } if(L != null && R != null){ return propNC(new long[4], L, R); } return L != null ? L : R; } } } public static class StarrySkyTreeL { public int M, H, N; public long[] st; public long[] plus; public long I = Long.MAX_VALUE/4; // I+plus<long public StarrySkyTreeL(int n) { N = n; M = Integer.highestOneBit(Math.max(n-1, 1))<<2; H = M>>>1; st = new long[M]; plus = new long[H]; } public StarrySkyTreeL(long[] a) { N = a.length; M = Integer.highestOneBit(Math.max(N-1, 1))<<2; H = M>>>1; st = new long[M]; for(int i = 0;i < N;i++){ st[H+i] = a[i]; } plus = new long[H]; Arrays.fill(st, H+N, M, I); for(int i = H-1;i >= 1;i--)propagate(i); } private void propagate(int i) { st[i] = Math.min(st[2*i], st[2*i+1]) + plus[i]; } public void add(int l, int r, long v){ if(l < r)add(l, r, v, 0, H, 1); } private void add(int l, int r, long v, int cl, int cr, int cur) { if(l <= cl && cr <= r){ if(cur >= H){ st[cur] += v; }else{ plus[cur] += v; propagate(cur); } }else{ int mid = cl+cr>>>1; if(cl < r && l < mid){ add(l, r, v, cl, mid, 2*cur); } if(mid < r && l < cr){ add(l, r, v, mid, cr, 2*cur+1); } propagate(cur); } } public long min(int l, int r){ return l >= r ? I : min(l, r, 0, H, 1);} private long min(int l, int r, int cl, int cr, int cur) { if(l <= cl && cr <= r){ return st[cur]; }else{ int mid = cl+cr>>>1; long ret = I; if(cl < r && l < mid){ ret = Math.min(ret, min(l, r, cl, mid, 2*cur)); } if(mid < r && l < cr){ ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1)); } return ret + plus[cur]; } } public void fall(int i) { if(i < H){ if(2*i < H){ plus[2*i] += plus[i]; plus[2*i+1] += plus[i]; } st[2*i] += plus[i]; st[2*i+1] += plus[i]; plus[i] = 0; } } public int firstle(int l, long v) { int cur = H+l; for(int i = 1, j = Integer.numberOfTrailingZeros(H)-1;i <= cur;j--){ fall(i); i = i*2|cur>>>j&1; } while(true){ fall(cur); if(st[cur] <= v){ if(cur < H){ cur = 2*cur; }else{ return cur-H; } }else{ cur++; if((cur&cur-1) == 0)return -1; cur = cur>>>Integer.numberOfTrailingZeros(cur); } } } public int lastle(int l, long v) { int cur = H+l; for(int i = 1, j = Integer.numberOfTrailingZeros(H)-1;i <= cur;j--){ fall(i); i = i*2|cur>>>j&1; } while(true){ fall(cur); if(st[cur] <= v){ if(cur < H){ cur = 2*cur+1; }else{ return cur-H; } }else{ if((cur&cur-1) == 0)return -1; cur = cur>>>Integer.numberOfTrailingZeros(cur); cur--; } } } public void addx(int l, int r, long v){ if(l >= r)return; while(l != 0){ int f = l&-l; if(l+f > r)break; if(f == 1){ st[(H+l)/f] += v; }else{ plus[(H+l)/f] += v; } l += f; } while(l < r){ int f = r&-r; if(f == 1){ st[(H+r)/f-1] += v; }else{ plus[(H+r)/f-1] += v; } r -= f; } } public long minx(int l, int r){ long lmin = I; if(l >= r)return lmin; if(l != 0){ for(int d = 0;H>>>d > 0;d++){ if(d > 0){ int id = (H+l-1>>>d); lmin += plus[id]; } if(l<<~d<0 && l+(1<<d) <= r){ long v = st[H+l>>>d]; if(v < lmin)lmin = v; l += 1<<d; } } } long rmin = I; for(int d = 0;H>>>d > 0;d++){ if(d > 0 && r < H)rmin += plus[H+r>>>d]; if(r<<~d<0 && l < r){ long v = st[(H+r>>>d)-1]; if(v < rmin)rmin = v; r -= 1<<d; } } long min = Math.min(lmin, rmin); return min; } public long[] toArray() { return toArray(1, 0, H, new long[H]); } private long[] toArray(int cur, int l, int r, long[] ret) { if(r-l == 1){ ret[cur-H] = st[cur]; }else{ toArray(2*cur, l, l+r>>>1, ret); toArray(2*cur+1, l+r>>>1, r, ret); for(int i = l;i < r;i++)ret[i] += plus[cur]; } return ret; } } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new Day24().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }