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
AC × 1
AC × 31
AC × 61
AC × 96
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