Submission #692365
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.List; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(); int[] a = na(n); out.println(doHuTucker(a)); } static class Datum { public int type; public int ind0, ind1; public long sum; public Datum(int type, int ind0, int ind1, long sum) { this.type = type; this.ind0 = ind0; this.ind1 = ind1; this.sum = sum; } @Override public String toString() { return "Datum [type=" + type + ", ind0=" + ind0 + ", ind1=" + ind1 + ", sum=" + sum + "]"; } } public static long doHuTucker(int[] a) { int n = a.length; // [0, leaf-index, leaf-index, sum] // [1, leaf-index, inner-node-index, sum] // [2, inner-node-index, sum] int gen = n; TaggedSimpleMinHeapL pq = new TaggedSimpleMinHeapL(8*n); // boolean[] merged = new boolean[n]; LST notMerged = new LST(n+1); notMerged.setRange(n+1); for(int i = 0;i < n-1;i++){ pq.add(new Datum(0, i, i+1, (long)a[i]+a[i+1]), (long)a[i]+a[i+1]); } // leaf 0 1 2 3 4 // inner 0 1 2 3 4 5 Node[] heaps = new Node[n+1]; long ret = 0; while(gen < 2*n-1){ Datum cur = pq.mintag(); pq.poll(); int low = -1; if(cur.type == 0){ if(!notMerged.get(cur.ind0+1) || !notMerged.get(cur.ind1+1))continue; // if(merged[cur.ind0] || merged[cur.ind1])continue; // merged[cur.ind0] = merged[cur.ind1] = true; notMerged.unset(cur.ind0+1); notMerged.unset(cur.ind1+1); low = notMerged.prev(cur.ind0+1); heaps[low] = merge(heaps[low], merge(heaps[cur.ind0+1], heaps[cur.ind1+1])); heaps[low] = merge(heaps[low], new Node(cur.sum)); heaps[cur.ind0+1] = null; heaps[cur.ind1+1] = null; }else if(cur.type == 1){ // if(merged[cur.ind0])continue; if(!notMerged.get(cur.ind0+1))continue; if(heaps[cur.ind1] == null)continue; if(heaps[cur.ind1].val + a[cur.ind0] != cur.sum)continue; heaps[cur.ind1] = deleteRoot(heaps[cur.ind1]); // merged[cur.ind0] = true; notMerged.unset(cur.ind0+1); low = notMerged.prev(cur.ind0+1); heaps[low] = merge(heaps[low], heaps[cur.ind0+1]); heaps[low] = merge(heaps[low], new Node(cur.sum)); heaps[cur.ind0+1] = null; }else if(cur.type == 2){ if(min2(heaps[cur.ind0]) == Long.MAX_VALUE)continue; if(min(heaps[cur.ind0]) + min2(heaps[cur.ind0]) != cur.sum)continue; Node min0 = heaps[cur.ind0]; Node min1 = deleteRoot(heaps[cur.ind0]); heaps[cur.ind0] = deleteRoot(min1); heaps[cur.ind0] = merge(heaps[cur.ind0], new Node(cur.sum)); low = cur.ind0; } int nex = notMerged.next(low+1); { long val = takeInner(heaps[low]); if(val != -1)pq.add(new Datum(2, low, -1, val), val); } if(low-1 != -1 && heaps[low] != null){ pq.add(new Datum(1, low-1, low, a[low-1] + heaps[low].val), a[low-1] + heaps[low].val); } if(nex != -1 && heaps[low] != null){ pq.add(new Datum(1, nex-1, low, a[nex-1] + heaps[low].val), a[nex-1] + heaps[low].val); } if(low-1 != -1 && nex != -1){ pq.add(new Datum(0, low-1, nex-1, (long)a[low-1] + a[nex-1]), (long)a[low-1] + a[nex-1]); } ret += cur.sum; gen++; } return ret; } static long takeInner(Node heap) { long min1 = min2(heap); if(min1 == Long.MAX_VALUE)return -1; return min(heap) + min1; } public static class Node { public long val; public Node left, right; public int dist; public Node(long x) { val = x; left = right = null; dist = 0; } public Node(Node n) { val = n.val; left = n.left; right = n.right; dist = n.dist; } public void disconnect() { left = right = null; dist = 0; } public String toString(String indent) { StringBuilder sb = new StringBuilder(); if(left != null)sb.append(left.toString(indent + " ")); sb.append(indent).append(val).append('\n'); if(right != null)sb.append(right.toString(indent + " ")); return sb.toString(); } } public static Node merge(Node m, Node n) { if(m == null)return n; if(n == null)return m; if(m.val > n.val){ // compare Node d = m; m = n; n = d; } // m = new Node(m); // if uncommented, heap becomes persistent. m.right = merge(m.right, n); if(m.left == null || m.right.dist > m.left.dist){ Node d = m.left; m.left = m.right; m.right = d; } m.dist = m.right == null ? 0 : m.right.dist + 1; return m; } public static long min(Node n) { return n != null ? n.val : Long.MAX_VALUE; } public static long min2(Node n) { if(n == null)return Long.MAX_VALUE; return Math.min(min(n.left), min(n.right)); } public static Node deleteRoot(Node n){ if(n == null)return null; Node ret = merge(n.left, n.right); n.disconnect(); return ret; } public static class TaggedSimpleMinHeapL { public long[] a; public Datum[] tags; public int n; public int pos; public static final long INF = Long.MAX_VALUE; public TaggedSimpleMinHeapL(int m) { n = m+1; a = new long[n]; tags = new Datum[n]; Arrays.fill(a, INF); pos = 1; } public void add(Datum tag, long x) { a[pos] = x; tags[pos] = tag; pos++; for(int c = pos-1, p = c>>>1;p >= 1 && a[c] < a[p];c>>>=1, p>>>=1){ {long d = a[p]; a[p] = a[c]; a[c] = d;} {Datum d = tags[p]; tags[p] = tags[c]; tags[c] = d;} } } public long poll() { if(pos == 1)return INF; pos--; long ret = a[1]; a[1] = a[pos]; a[pos] = INF; tags[1] = tags[pos]; tags[pos] = null; for(int c = 1;2*c < pos;){ int smaller = a[2*c] < a[2*c+1] ? 2*c : 2*c+1; if(a[smaller] < a[c]){ {long d = a[c]; a[c] = a[smaller]; a[smaller] = d;} {Datum d = tags[c]; tags[c] = tags[smaller]; tags[smaller] = d;} c = smaller; }else{ break; } } return ret; } public long min() { return a[1]; } public Datum mintag() { return tags[1]; } public int size() { return pos-1; } } public static class LST { public long[][] set; public int n; // public int size; public LST(int n) { this.n = n; int d = 1; for(int m = n;m > 1;m>>>=6, d++); set = new long[d][]; for(int i = 0, m = n>>>6;i < d;i++, m>>>=6){ set[i] = new long[m+1]; } // size = 0; } // [0,r) public LST setRange(int r) { for(int i = 0;i < set.length;i++, r=r+63>>>6){ for(int j = 0;j < r>>>6;j++){ set[i][j] = -1L; } if((r&63) != 0)set[i][r>>>6] |= (1L<<r)-1; } return this; } // [0,r) public LST unsetRange(int r) { if(r >= 0){ for(int i = 0;i < set.length;i++, r=r+63>>>6){ for(int j = 0;j < r+63>>>6;j++){ set[i][j] = 0; } if((r&63) != 0)set[i][r>>>6] &= ~((1L<<r)-1); } } return this; } public LST set(int pos) { if(pos >= 0 && pos < n){ // if(!get(pos))size++; for(int i = 0;i < set.length;i++, pos>>>=6){ set[i][pos>>>6] |= 1L<<pos; } } return this; } public LST unset(int pos) { if(pos >= 0 && pos < n){ // if(get(pos))size--; for(int i = 0;i < set.length && (i == 0 || set[i-1][pos] == 0L);i++, pos>>>=6){ set[i][pos>>>6] &= ~(1L<<pos); } } return this; } public boolean get(int pos) { return pos >= 0 && pos < n && set[0][pos>>>6]<<~pos<0; } public int prev(int pos) { for(int i = 0;i < set.length && pos >= 0;i++, pos>>>=6, pos--){ int pre = prev(set[i][pos>>>6], pos&63); if(pre != -1){ pos = pos>>>6<<6|pre; while(i > 0)pos = pos<<6|63-Long.numberOfLeadingZeros(set[--i][pos]); return pos; } } return -1; } public int next(int pos) { for(int i = 0;i < set.length && pos>>>6 < set[i].length;i++, pos>>>=6, pos++){ int nex = next(set[i][pos>>>6], pos&63); if(nex != -1){ pos = pos>>>6<<6|nex; while(i > 0)pos = pos<<6|Long.numberOfTrailingZeros(set[--i][pos]); return pos; } } return -1; } private static int prev(long set, int n) { long h = Long.highestOneBit(set<<~n); if(h == 0L)return -1; return Long.numberOfTrailingZeros(h)-(63-n); } private static int next(long set, int n) { long h = Long.lowestOneBit(set>>>n); if(h == 0L)return -1; return Long.numberOfTrailingZeros(h)+n; } @Override public String toString() { List<Integer> list = new ArrayList<Integer>(); for(int pos = next(0);pos != -1;pos = next(pos+1)){ list.add(pos); } return list.toString(); } } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static 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 static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static 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 static 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 static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, 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 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) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | uwi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 101 |
Code Size | 12152 Byte |
Status | AC |
Exec Time | 561 ms |
Memory | 43492 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 160 ms | 8144 KB |
01_00.txt | AC | 166 ms | 8276 KB |
01_01.txt | AC | 166 ms | 8148 KB |
01_02.txt | AC | 164 ms | 8148 KB |
01_03.txt | AC | 161 ms | 8276 KB |
01_04.txt | AC | 161 ms | 8148 KB |
01_05.txt | AC | 161 ms | 8148 KB |
01_06.txt | AC | 165 ms | 8276 KB |
01_07.txt | AC | 163 ms | 8144 KB |
01_08.txt | AC | 162 ms | 8148 KB |
01_09.txt | AC | 162 ms | 8148 KB |
01_10.txt | AC | 162 ms | 8148 KB |
01_11.txt | AC | 161 ms | 8148 KB |
01_12.txt | AC | 163 ms | 8148 KB |
01_13.txt | AC | 162 ms | 8276 KB |
01_14.txt | AC | 163 ms | 8148 KB |
01_15.txt | AC | 162 ms | 8148 KB |
01_16.txt | AC | 163 ms | 8148 KB |
01_17.txt | AC | 162 ms | 8148 KB |
01_18.txt | AC | 160 ms | 8148 KB |
01_19.txt | AC | 156 ms | 8148 KB |
01_20.txt | AC | 155 ms | 8148 KB |
01_21.txt | AC | 149 ms | 8272 KB |
01_22.txt | AC | 166 ms | 8020 KB |
01_23.txt | AC | 155 ms | 8276 KB |
01_24.txt | AC | 162 ms | 8276 KB |
01_25.txt | AC | 159 ms | 8148 KB |
01_26.txt | AC | 158 ms | 8144 KB |
01_27.txt | AC | 154 ms | 8276 KB |
01_28.txt | AC | 159 ms | 8148 KB |
01_29.txt | AC | 167 ms | 8148 KB |
02_00.txt | AC | 199 ms | 9300 KB |
02_01.txt | AC | 192 ms | 9172 KB |
02_02.txt | AC | 187 ms | 9172 KB |
02_03.txt | AC | 189 ms | 9300 KB |
02_04.txt | AC | 195 ms | 9428 KB |
02_05.txt | AC | 183 ms | 9044 KB |
02_06.txt | AC | 188 ms | 9300 KB |
02_07.txt | AC | 178 ms | 9172 KB |
02_08.txt | AC | 187 ms | 9168 KB |
02_09.txt | AC | 195 ms | 9300 KB |
02_10.txt | AC | 187 ms | 9172 KB |
02_11.txt | AC | 188 ms | 9172 KB |
02_12.txt | AC | 196 ms | 9428 KB |
02_13.txt | AC | 180 ms | 9428 KB |
02_14.txt | AC | 184 ms | 9172 KB |
02_15.txt | AC | 188 ms | 9172 KB |
02_16.txt | AC | 192 ms | 9044 KB |
02_17.txt | AC | 188 ms | 9172 KB |
02_18.txt | AC | 180 ms | 9296 KB |
02_19.txt | AC | 180 ms | 9172 KB |
02_20.txt | AC | 174 ms | 9172 KB |
02_21.txt | AC | 180 ms | 9428 KB |
02_22.txt | AC | 199 ms | 9296 KB |
02_23.txt | AC | 177 ms | 9172 KB |
02_24.txt | AC | 184 ms | 9172 KB |
02_25.txt | AC | 180 ms | 9172 KB |
02_26.txt | AC | 188 ms | 9172 KB |
02_27.txt | AC | 196 ms | 9164 KB |
02_28.txt | AC | 180 ms | 9168 KB |
02_29.txt | AC | 196 ms | 9428 KB |
03_00.txt | AC | 505 ms | 43384 KB |
03_01.txt | AC | 518 ms | 42792 KB |
03_02.txt | AC | 516 ms | 43492 KB |
03_03.txt | AC | 515 ms | 43144 KB |
03_04.txt | AC | 493 ms | 43112 KB |
03_05.txt | AC | 447 ms | 41300 KB |
03_06.txt | AC | 503 ms | 39648 KB |
03_07.txt | AC | 518 ms | 39652 KB |
03_08.txt | AC | 492 ms | 39716 KB |
03_09.txt | AC | 484 ms | 39720 KB |
03_10.txt | AC | 480 ms | 39860 KB |
03_11.txt | AC | 485 ms | 38976 KB |
03_12.txt | AC | 523 ms | 39752 KB |
03_13.txt | AC | 528 ms | 40652 KB |
03_14.txt | AC | 510 ms | 40556 KB |
03_15.txt | AC | 475 ms | 40520 KB |
03_16.txt | AC | 492 ms | 40600 KB |
03_17.txt | AC | 516 ms | 40932 KB |
03_18.txt | AC | 492 ms | 40160 KB |
03_19.txt | AC | 505 ms | 41036 KB |
03_20.txt | AC | 512 ms | 40928 KB |
03_21.txt | AC | 504 ms | 40840 KB |
03_22.txt | AC | 500 ms | 41136 KB |
03_23.txt | AC | 534 ms | 39328 KB |
03_24.txt | AC | 561 ms | 39680 KB |
03_25.txt | AC | 540 ms | 40548 KB |
03_26.txt | AC | 523 ms | 40992 KB |
03_27.txt | AC | 499 ms | 40332 KB |
03_28.txt | AC | 539 ms | 41308 KB |
03_29.txt | AC | 530 ms | 41036 KB |
03_30.txt | AC | 498 ms | 40332 KB |
03_31.txt | AC | 532 ms | 40844 KB |
03_32.txt | AC | 538 ms | 40808 KB |
03_33.txt | AC | 515 ms | 41260 KB |
03_34.txt | AC | 496 ms | 40500 KB |