import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class sia { public static void main(final String ... args) throws Exception { final BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line = in.readLine(); String[] sizes = line.split(" "); long m = Long.parseLong(sizes[1]); line = in.readLine(); String[] fieldAsText = line.split(" "); long[] growth = new long[fieldAsText.length]; long[] dayCut = new long[fieldAsText.length]; long[] cutTo = new long[fieldAsText.length]; for(int i = 0; i < fieldAsText.length; i++) { growth[i] = Long.parseLong(fieldAsText[i]); } Arrays.sort(growth); long prevD = 0; int cutToIndex = fieldAsText.length; for(int j = 0; j < m; j++) { line = in.readLine(); sizes = line.split(" "); long d = Long.parseLong(sizes[0]); long b = Long.parseLong(sizes[1]); int cutFromIndex = binarySearch(growth, dayCut, cutTo, d, b + 1); long sum = 0; for(int i = cutFromIndex; i < fieldAsText.length; i++) { sum += growth[i] * (d - dayCut[i]) + cutTo[i] - b; dayCut[i] = d; cutTo[i] = b; } System.out.println(sum); prevD = d; } in.close(); } private static int binarySearch(long[] growth, long[] dayCut, long[] cutTo, long day, long cut) { int low = 0; int high = growth.length - 1; while (low <= high) { int mid = (low + high) >>> 1; long midVal = growth[mid] * (day - dayCut[mid]) + cutTo[mid]; if (midVal < cut) low = mid + 1; else if (midVal > cut) high = mid - 1; else return mid; } if (low >= growth.length) { return low; } else if (growth[low] * (day - dayCut[low]) + cutTo[low] >= cut) { return low; } else { return low + 1; } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class sia { public static void main(final String ... args) throws Exception { final BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line = in.readLine(); String[] sizes = line.split(" "); long m = Long.parseLong(sizes[1]); line = in.readLine(); String[] fieldAsText = line.split(" "); long[] growth = new long[fieldAsText.length]; long[] dayCut = new long[fieldAsText.length]; long[] cutTo = new long[fieldAsText.length]; for(int i = 0; i < fieldAsText.length; i++) { growth[i] = Long.parseLong(fieldAsText[i]); } Arrays.sort(growth); long prevD = 0; int cutToIndex = fieldAsText.length; for(int j = 0; j < m; j++) { line = in.readLine(); sizes = line.split(" "); long d = Long.parseLong(sizes[0]); long b = Long.parseLong(sizes[1]); int cutFromIndex = binarySearch(growth, dayCut, cutTo, d, b + 1); long sum = 0; for(int i = cutFromIndex; i < fieldAsText.length; i++) { sum += growth[i] * (d - dayCut[i]) + cutTo[i] - b; dayCut[i] = d; cutTo[i] = b; } System.out.println(sum); prevD = d; } in.close(); } private static int binarySearch(long[] growth, long[] dayCut, long[] cutTo, long day, long cut) { int low = 0; int high = growth.length - 1; while (low <= high) { int mid = (low + high) >>> 1; long midVal = growth[mid] * (day - dayCut[mid]) + cutTo[mid]; if (midVal < cut) low = mid + 1; else if (midVal > cut) high = mid - 1; else return mid; } if (low >= growth.length) { return low; } else if (growth[low] * (day - dayCut[low]) + cutTo[low] >= cut) { return low; } else { return low + 1; } } } |