Submission #617434
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.InputMismatchException; import java.util.Queue; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve(){ int n = ni(); int L = ni(); int[] a = new int[n]; int[] t = new int[n]; for(int i = 0;i < n;i++){ t[i] = ni(); a[i] = ni(); } Node[][] h = new Node[n][2]; // max,min int[][] num = new int[n][2]; int p = 0; for(int i = 0;i < n;){ Node maxh = null; Node minh = null; int j = i; while(j < n && t[i] == t[j])j++; Arrays.sort(a, i, j); for(int k = i;k < i+(j-i)/2;k++){ maxh = merge(maxh, new Node(-a[k])); } for(int k = i+(j-i)/2;k < j;k++){ minh = merge(minh, new Node(a[k])); } int nmaxh = (j-i)/2; int nminh = j-i-nmaxh; assert nmaxh <= nminh && nmaxh + nminh == j-i; while(true){ int mid = minh.key; if(p == 0 || h[p-1][1].key < mid){ h[p][0] = maxh; h[p][1] = minh; num[p][0] = nmaxh; num[p][1] = nminh; p++; break; }else{ p--; maxh = merge(maxh, h[p][0]); minh = merge(minh, h[p][1]); nmaxh += num[p][0]; nminh += num[p][1]; // balance while(nminh - nmaxh > 1){ Node headmin = minh; minh = deleteRoot(minh); headmin.key = -headmin.key; maxh = merge(maxh, headmin); nmaxh++; nminh--; } // swap while(-min(maxh) > min(minh)){ Node headmin = minh; Node headmax = maxh; minh = deleteRoot(minh); maxh = deleteRoot(maxh); headmin.key = -headmin.key; headmax.key = -headmax.key; minh = merge(minh, headmax); maxh = merge(maxh, headmin); } h[p][0] = h[p][1] = null; num[p][0] = 0; num[p][1] = 0; } } i = j; } long ret = 0; int q = 0; for(int i = 0;i < p;i++){ for(int j = 0;j < num[i][0]+num[i][1];j++, q++){ ret += Math.abs(a[q]-h[i][1].key); } } // if(q != n)throw new AssertionError(q + " " + n); out.println(ret); } public static class Node { public int key; public Node left, right; public int dist; public Node(int x) { key = x; left = right = null; dist = 0; } public void disconnect() { left = right = null; dist = 0; } } public static Node merge(Node m, Node n) { if(m == null)return n; if(n == null)return m; if(m.key > n.key){ Node d = m; m = n; n = d; } 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 Node insert(int x, Node n) { return merge(n, new Node(x)); } public static int min(Node n) { return n != null ? n.key : Integer.MAX_VALUE; } public static Node deleteRoot(Node n){ if(n == null)return null; Node ret = merge(n.left, n.right); n.disconnect(); return ret; } public static Node build(int[] a) { if(a.length == 0)return null; Queue<Node> q = new ArrayDeque<Node>(); for(int x : a)q.add(new Node(x)); while(q.size() > 1){ q.add(merge(q.poll(), q.poll())); } return q.poll(); } 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 | E - 花火 |
User | uwi |
Language | Java (OpenJDK 1.7.0) |
Score | 160 |
Code Size | 6610 Byte |
Status | AC |
Exec Time | 2202 ms |
Memory | 47156 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 130 / 130 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt |
Subtask2 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt, subtask2_50.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 329 ms | 22860 KB |
sample_02.txt | AC | 327 ms | 22852 KB |
sample_03.txt | AC | 324 ms | 22920 KB |
subtask1_01.txt | AC | 361 ms | 24884 KB |
subtask1_02.txt | AC | 343 ms | 24756 KB |
subtask1_03.txt | AC | 361 ms | 24176 KB |
subtask1_04.txt | AC | 354 ms | 24672 KB |
subtask1_05.txt | AC | 356 ms | 24880 KB |
subtask1_06.txt | AC | 356 ms | 24772 KB |
subtask1_07.txt | AC | 343 ms | 24900 KB |
subtask1_08.txt | AC | 339 ms | 24192 KB |
subtask1_09.txt | AC | 342 ms | 24008 KB |
subtask1_10.txt | AC | 343 ms | 23832 KB |
subtask1_11.txt | AC | 352 ms | 23856 KB |
subtask1_12.txt | AC | 358 ms | 23800 KB |
subtask1_13.txt | AC | 346 ms | 23836 KB |
subtask1_14.txt | AC | 351 ms | 23588 KB |
subtask1_15.txt | AC | 356 ms | 23904 KB |
subtask1_16.txt | AC | 369 ms | 24528 KB |
subtask1_17.txt | AC | 354 ms | 24600 KB |
subtask1_18.txt | AC | 360 ms | 24364 KB |
subtask1_19.txt | AC | 337 ms | 24424 KB |
subtask1_20.txt | AC | 345 ms | 24720 KB |
subtask1_21.txt | AC | 346 ms | 23980 KB |
subtask1_22.txt | AC | 335 ms | 23744 KB |
subtask1_23.txt | AC | 333 ms | 24040 KB |
subtask1_24.txt | AC | 344 ms | 24896 KB |
subtask1_25.txt | AC | 342 ms | 24912 KB |
subtask1_26.txt | AC | 395 ms | 24276 KB |
subtask1_27.txt | AC | 348 ms | 24608 KB |
subtask1_28.txt | AC | 367 ms | 23928 KB |
subtask1_29.txt | AC | 340 ms | 23852 KB |
subtask1_30.txt | AC | 353 ms | 24916 KB |
subtask1_31.txt | AC | 348 ms | 24864 KB |
subtask1_32.txt | AC | 349 ms | 24788 KB |
subtask1_33.txt | AC | 348 ms | 24868 KB |
subtask1_34.txt | AC | 352 ms | 24448 KB |
subtask1_35.txt | AC | 344 ms | 24008 KB |
subtask1_36.txt | AC | 364 ms | 24536 KB |
subtask1_37.txt | AC | 329 ms | 22840 KB |
subtask1_38.txt | AC | 327 ms | 22940 KB |
subtask1_39.txt | AC | 2202 ms | 22820 KB |
subtask1_40.txt | AC | 331 ms | 22824 KB |
subtask1_41.txt | AC | 336 ms | 22904 KB |
subtask1_42.txt | AC | 327 ms | 22864 KB |
subtask2_01.txt | AC | 680 ms | 46552 KB |
subtask2_02.txt | AC | 655 ms | 46472 KB |
subtask2_03.txt | AC | 677 ms | 45892 KB |
subtask2_04.txt | AC | 1034 ms | 46332 KB |
subtask2_05.txt | AC | 658 ms | 45904 KB |
subtask2_06.txt | AC | 624 ms | 45552 KB |
subtask2_07.txt | AC | 579 ms | 37796 KB |
subtask2_08.txt | AC | 477 ms | 34712 KB |
subtask2_09.txt | AC | 667 ms | 45788 KB |
subtask2_10.txt | AC | 645 ms | 46108 KB |
subtask2_11.txt | AC | 648 ms | 45788 KB |
subtask2_12.txt | AC | 645 ms | 45884 KB |
subtask2_13.txt | AC | 667 ms | 46124 KB |
subtask2_14.txt | AC | 494 ms | 42516 KB |
subtask2_15.txt | AC | 479 ms | 42072 KB |
subtask2_16.txt | AC | 475 ms | 42036 KB |
subtask2_17.txt | AC | 479 ms | 42344 KB |
subtask2_18.txt | AC | 551 ms | 45624 KB |
subtask2_19.txt | AC | 486 ms | 39956 KB |
subtask2_20.txt | AC | 490 ms | 43636 KB |
subtask2_21.txt | AC | 511 ms | 43996 KB |
subtask2_22.txt | AC | 522 ms | 44768 KB |
subtask2_23.txt | AC | 545 ms | 45864 KB |
subtask2_24.txt | AC | 694 ms | 45512 KB |
subtask2_25.txt | AC | 639 ms | 45496 KB |
subtask2_26.txt | AC | 706 ms | 45860 KB |
subtask2_27.txt | AC | 711 ms | 45920 KB |
subtask2_28.txt | AC | 702 ms | 45956 KB |
subtask2_29.txt | AC | 503 ms | 43868 KB |
subtask2_30.txt | AC | 537 ms | 47156 KB |
subtask2_31.txt | AC | 512 ms | 43936 KB |
subtask2_32.txt | AC | 673 ms | 45880 KB |
subtask2_33.txt | AC | 677 ms | 46032 KB |
subtask2_34.txt | AC | 542 ms | 43920 KB |
subtask2_35.txt | AC | 666 ms | 46448 KB |
subtask2_36.txt | AC | 760 ms | 45896 KB |
subtask2_37.txt | AC | 716 ms | 45956 KB |
subtask2_38.txt | AC | 633 ms | 44528 KB |
subtask2_39.txt | AC | 560 ms | 43084 KB |
subtask2_40.txt | AC | 463 ms | 39952 KB |
subtask2_41.txt | AC | 673 ms | 44944 KB |
subtask2_42.txt | AC | 727 ms | 45288 KB |
subtask2_43.txt | AC | 772 ms | 45160 KB |
subtask2_44.txt | AC | 611 ms | 43136 KB |
subtask2_45.txt | AC | 709 ms | 44932 KB |
subtask2_46.txt | AC | 488 ms | 40084 KB |
subtask2_47.txt | AC | 694 ms | 45084 KB |
subtask2_48.txt | AC | 333 ms | 22924 KB |
subtask2_49.txt | AC | 345 ms | 22800 KB |
subtask2_50.txt | AC | 345 ms | 22880 KB |