Submission #692352
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.Comparator; import java.util.InputMismatchException; import java.util.List; import java.util.PriorityQueue; 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; PriorityQueue<Datum> pq = new PriorityQueue<Datum>(n, new Comparator<Datum>(){ public int compare(Datum x, Datum y) { return Long.compare(x.sum, y.sum); } }); 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])); } // leaf 0 1 2 3 4 // inner 0 1 2 3 4 5 Node[] heaps = new Node[n+1]; int[] par = new int[2*n-1]; while(gen < 2*n-1){ Datum cur = pq.poll(); int low = -1; if(cur.type == 0){ 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, gen)); par[cur.ind0] = par[cur.ind1] = gen; heaps[cur.ind0+1] = null; heaps[cur.ind1+1] = null; }else if(cur.type == 1){ if(merged[cur.ind0])continue; if(heaps[cur.ind1] == null)continue; if(heaps[cur.ind1].val + a[cur.ind0] != cur.sum)continue; par[cur.ind0] = par[heaps[cur.ind1].id] = gen; 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, gen)); 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); par[min0.id] = par[min1.id] = gen; heaps[cur.ind0] = merge(heaps[cur.ind0], new Node(cur.sum, gen)); 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)); } if(low-1 != -1 && heaps[low] != null){ pq.add(new Datum(1, low-1, low, 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)); } if(low-1 != -1 && nex != -1){ pq.add(new Datum(0, low-1, nex-1, (long)a[low-1] + a[nex-1])); } gen++; } int[] dep = new int[2*n-1]; for(int i = 2*n-3;i >= 0;i--){ dep[i] = dep[par[i]] + 1; } int[][] di = new int[n][]; for(int i = 0;i < n;i++){ di[i] = new int[]{dep[i], i}; } Arrays.sort(di, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return -(a[0] - b[0]); } }); LST alive = new LST(n+2); long[] mval = new long[n]; long ret = 0; int i = 0; out: for(int d = di[0][0];;d--){ int j = i; while(j < n && di[j][0] == d){ alive.set(di[j][1]); mval[di[j][1]] = a[di[j][1]]; j++; } for(int k = alive.next(0);k != -1;k = alive.next(k+1)){ int l = alive.next(k+1); if(l == -1)break out; mval[k] += mval[l]; ret += mval[k]; alive.unset(l); } i = j; } 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 int id; public Node(long x, int id) { val = x; left = right = null; dist = 0; this.id = id; } public Node(Node n) { val = n.val; left = n.left; right = n.right; dist = n.dist; id = n.id; } 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 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 | 11870 Byte |
Status | AC |
Exec Time | 886 ms |
Memory | 42368 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 | 152 ms | 8272 KB |
01_00.txt | AC | 160 ms | 8272 KB |
01_01.txt | AC | 160 ms | 8276 KB |
01_02.txt | AC | 156 ms | 8268 KB |
01_03.txt | AC | 160 ms | 8268 KB |
01_04.txt | AC | 156 ms | 8144 KB |
01_05.txt | AC | 160 ms | 8276 KB |
01_06.txt | AC | 158 ms | 8276 KB |
01_07.txt | AC | 164 ms | 8404 KB |
01_08.txt | AC | 158 ms | 8272 KB |
01_09.txt | AC | 162 ms | 8272 KB |
01_10.txt | AC | 171 ms | 8272 KB |
01_11.txt | AC | 157 ms | 8272 KB |
01_12.txt | AC | 167 ms | 8148 KB |
01_13.txt | AC | 167 ms | 8268 KB |
01_14.txt | AC | 167 ms | 8272 KB |
01_15.txt | AC | 167 ms | 8272 KB |
01_16.txt | AC | 168 ms | 8268 KB |
01_17.txt | AC | 164 ms | 8272 KB |
01_18.txt | AC | 159 ms | 8148 KB |
01_19.txt | AC | 167 ms | 8272 KB |
01_20.txt | AC | 167 ms | 8268 KB |
01_21.txt | AC | 160 ms | 8276 KB |
01_22.txt | AC | 158 ms | 8272 KB |
01_23.txt | AC | 167 ms | 8272 KB |
01_24.txt | AC | 171 ms | 8264 KB |
01_25.txt | AC | 160 ms | 8276 KB |
01_26.txt | AC | 160 ms | 8276 KB |
01_27.txt | AC | 159 ms | 8144 KB |
01_28.txt | AC | 168 ms | 8272 KB |
01_29.txt | AC | 160 ms | 8276 KB |
02_00.txt | AC | 192 ms | 9684 KB |
02_01.txt | AC | 204 ms | 9684 KB |
02_02.txt | AC | 205 ms | 9812 KB |
02_03.txt | AC | 215 ms | 9684 KB |
02_04.txt | AC | 208 ms | 9552 KB |
02_05.txt | AC | 208 ms | 9684 KB |
02_06.txt | AC | 200 ms | 9556 KB |
02_07.txt | AC | 212 ms | 9556 KB |
02_08.txt | AC | 204 ms | 9680 KB |
02_09.txt | AC | 195 ms | 9684 KB |
02_10.txt | AC | 200 ms | 9684 KB |
02_11.txt | AC | 204 ms | 9556 KB |
02_12.txt | AC | 200 ms | 9808 KB |
02_13.txt | AC | 212 ms | 9552 KB |
02_14.txt | AC | 208 ms | 9808 KB |
02_15.txt | AC | 200 ms | 9804 KB |
02_16.txt | AC | 212 ms | 9680 KB |
02_17.txt | AC | 208 ms | 9556 KB |
02_18.txt | AC | 198 ms | 9684 KB |
02_19.txt | AC | 204 ms | 9684 KB |
02_20.txt | AC | 200 ms | 9556 KB |
02_21.txt | AC | 208 ms | 9812 KB |
02_22.txt | AC | 220 ms | 9808 KB |
02_23.txt | AC | 208 ms | 9684 KB |
02_24.txt | AC | 203 ms | 9552 KB |
02_25.txt | AC | 212 ms | 9684 KB |
02_26.txt | AC | 196 ms | 9680 KB |
02_27.txt | AC | 208 ms | 9684 KB |
02_28.txt | AC | 208 ms | 9684 KB |
02_29.txt | AC | 211 ms | 9684 KB |
03_00.txt | AC | 759 ms | 41424 KB |
03_01.txt | AC | 717 ms | 42368 KB |
03_02.txt | AC | 664 ms | 40680 KB |
03_03.txt | AC | 720 ms | 40600 KB |
03_04.txt | AC | 671 ms | 40508 KB |
03_05.txt | AC | 695 ms | 41296 KB |
03_06.txt | AC | 678 ms | 36100 KB |
03_07.txt | AC | 859 ms | 38872 KB |
03_08.txt | AC | 620 ms | 38716 KB |
03_09.txt | AC | 599 ms | 38348 KB |
03_10.txt | AC | 560 ms | 38560 KB |
03_11.txt | AC | 550 ms | 38292 KB |
03_12.txt | AC | 700 ms | 36368 KB |
03_13.txt | AC | 615 ms | 38776 KB |
03_14.txt | AC | 738 ms | 39848 KB |
03_15.txt | AC | 670 ms | 37092 KB |
03_16.txt | AC | 624 ms | 40156 KB |
03_17.txt | AC | 631 ms | 41928 KB |
03_18.txt | AC | 667 ms | 36936 KB |
03_19.txt | AC | 724 ms | 39256 KB |
03_20.txt | AC | 637 ms | 37980 KB |
03_21.txt | AC | 886 ms | 40600 KB |
03_22.txt | AC | 632 ms | 40388 KB |
03_23.txt | AC | 668 ms | 40400 KB |
03_24.txt | AC | 651 ms | 38616 KB |
03_25.txt | AC | 640 ms | 38240 KB |
03_26.txt | AC | 715 ms | 38652 KB |
03_27.txt | AC | 639 ms | 38888 KB |
03_28.txt | AC | 620 ms | 39268 KB |
03_29.txt | AC | 600 ms | 40652 KB |
03_30.txt | AC | 695 ms | 38704 KB |
03_31.txt | AC | 695 ms | 38752 KB |
03_32.txt | AC | 772 ms | 41212 KB |
03_33.txt | AC | 775 ms | 40904 KB |
03_34.txt | AC | 699 ms | 39504 KB |