Submission #618544
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.PriorityQueue; 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(); } PriorityQueue<Long> pq = new PriorityQueue<>(); int mid = 0; long ret = 0; for(int i = 0;i < n;){ int j = i; while(j < n && t[i] == t[j])j++; for(int k = i;k < j;k++){ pq.add(-((long)a[k]<<32|k)); pq.add(-((long)a[k]<<32|k)); } long c = 0; while(pq.size() > j){ long polled = -pq.poll(); if((int)polled < i && polled>>>32 <= mid)c++; // only old elements can affect. long nex = -pq.peek(); if(nex>>>32 <= mid){ ret += (mid-(nex>>>32))*c; mid = (int)(nex>>>32); } } mid = (int)((-pq.peek())>>>32); for(int k = i;k < j;k++){ ret += Math.abs(a[k]-mid); } i = j; } out.println(ret); } 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 | 4299 Byte |
Status | AC |
Exec Time | 719 ms |
Memory | 36872 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 | 487 ms | 22648 KB |
sample_02.txt | AC | 326 ms | 22672 KB |
sample_03.txt | AC | 340 ms | 22744 KB |
subtask1_01.txt | AC | 374 ms | 24736 KB |
subtask1_02.txt | AC | 365 ms | 24816 KB |
subtask1_03.txt | AC | 378 ms | 24788 KB |
subtask1_04.txt | AC | 375 ms | 24796 KB |
subtask1_05.txt | AC | 417 ms | 24540 KB |
subtask1_06.txt | AC | 364 ms | 24724 KB |
subtask1_07.txt | AC | 373 ms | 24608 KB |
subtask1_08.txt | AC | 368 ms | 24672 KB |
subtask1_09.txt | AC | 376 ms | 24588 KB |
subtask1_10.txt | AC | 375 ms | 24756 KB |
subtask1_11.txt | AC | 365 ms | 24584 KB |
subtask1_12.txt | AC | 371 ms | 24624 KB |
subtask1_13.txt | AC | 364 ms | 24264 KB |
subtask1_14.txt | AC | 369 ms | 24408 KB |
subtask1_15.txt | AC | 363 ms | 24600 KB |
subtask1_16.txt | AC | 372 ms | 24624 KB |
subtask1_17.txt | AC | 382 ms | 24768 KB |
subtask1_18.txt | AC | 381 ms | 24616 KB |
subtask1_19.txt | AC | 377 ms | 24860 KB |
subtask1_20.txt | AC | 381 ms | 24620 KB |
subtask1_21.txt | AC | 379 ms | 24832 KB |
subtask1_22.txt | AC | 377 ms | 24696 KB |
subtask1_23.txt | AC | 380 ms | 24644 KB |
subtask1_24.txt | AC | 376 ms | 24748 KB |
subtask1_25.txt | AC | 375 ms | 24644 KB |
subtask1_26.txt | AC | 374 ms | 24804 KB |
subtask1_27.txt | AC | 369 ms | 24600 KB |
subtask1_28.txt | AC | 383 ms | 24876 KB |
subtask1_29.txt | AC | 377 ms | 24316 KB |
subtask1_30.txt | AC | 374 ms | 24368 KB |
subtask1_31.txt | AC | 378 ms | 24604 KB |
subtask1_32.txt | AC | 379 ms | 24912 KB |
subtask1_33.txt | AC | 388 ms | 24536 KB |
subtask1_34.txt | AC | 376 ms | 24428 KB |
subtask1_35.txt | AC | 375 ms | 24816 KB |
subtask1_36.txt | AC | 372 ms | 24492 KB |
subtask1_37.txt | AC | 331 ms | 22628 KB |
subtask1_38.txt | AC | 332 ms | 22572 KB |
subtask1_39.txt | AC | 331 ms | 22640 KB |
subtask1_40.txt | AC | 337 ms | 22612 KB |
subtask1_41.txt | AC | 353 ms | 22668 KB |
subtask1_42.txt | AC | 332 ms | 22696 KB |
subtask2_01.txt | AC | 504 ms | 35340 KB |
subtask2_02.txt | AC | 507 ms | 35328 KB |
subtask2_03.txt | AC | 502 ms | 35672 KB |
subtask2_04.txt | AC | 502 ms | 35264 KB |
subtask2_05.txt | AC | 503 ms | 35212 KB |
subtask2_06.txt | AC | 476 ms | 30132 KB |
subtask2_07.txt | AC | 462 ms | 28504 KB |
subtask2_08.txt | AC | 526 ms | 27400 KB |
subtask2_09.txt | AC | 533 ms | 35592 KB |
subtask2_10.txt | AC | 537 ms | 35740 KB |
subtask2_11.txt | AC | 552 ms | 35392 KB |
subtask2_12.txt | AC | 719 ms | 35712 KB |
subtask2_13.txt | AC | 556 ms | 35532 KB |
subtask2_14.txt | AC | 526 ms | 36612 KB |
subtask2_15.txt | AC | 562 ms | 36408 KB |
subtask2_16.txt | AC | 508 ms | 36276 KB |
subtask2_17.txt | AC | 513 ms | 36108 KB |
subtask2_18.txt | AC | 499 ms | 35676 KB |
subtask2_19.txt | AC | 515 ms | 36872 KB |
subtask2_20.txt | AC | 550 ms | 36328 KB |
subtask2_21.txt | AC | 515 ms | 36032 KB |
subtask2_22.txt | AC | 517 ms | 36416 KB |
subtask2_23.txt | AC | 504 ms | 31320 KB |
subtask2_24.txt | AC | 502 ms | 35308 KB |
subtask2_25.txt | AC | 503 ms | 35800 KB |
subtask2_26.txt | AC | 502 ms | 35276 KB |
subtask2_27.txt | AC | 540 ms | 36840 KB |
subtask2_28.txt | AC | 507 ms | 35568 KB |
subtask2_29.txt | AC | 525 ms | 36084 KB |
subtask2_30.txt | AC | 522 ms | 36232 KB |
subtask2_31.txt | AC | 503 ms | 35980 KB |
subtask2_32.txt | AC | 508 ms | 35648 KB |
subtask2_33.txt | AC | 509 ms | 35660 KB |
subtask2_34.txt | AC | 499 ms | 36008 KB |
subtask2_35.txt | AC | 513 ms | 35660 KB |
subtask2_36.txt | AC | 506 ms | 35804 KB |
subtask2_37.txt | AC | 544 ms | 35676 KB |
subtask2_38.txt | AC | 510 ms | 35684 KB |
subtask2_39.txt | AC | 533 ms | 36824 KB |
subtask2_40.txt | AC | 533 ms | 36500 KB |
subtask2_41.txt | AC | 524 ms | 35496 KB |
subtask2_42.txt | AC | 527 ms | 35668 KB |
subtask2_43.txt | AC | 519 ms | 35324 KB |
subtask2_44.txt | AC | 533 ms | 36552 KB |
subtask2_45.txt | AC | 508 ms | 35352 KB |
subtask2_46.txt | AC | 540 ms | 36400 KB |
subtask2_47.txt | AC | 516 ms | 35528 KB |
subtask2_48.txt | AC | 337 ms | 22712 KB |
subtask2_49.txt | AC | 339 ms | 22664 KB |
subtask2_50.txt | AC | 332 ms | 22668 KB |