#include "stdio.h" #include "stdlib.h" int T = 0; int K = 0; int W[510000]; long long sumW[510000]; long long D[510000]; long long H[510000]; int cutIdx[1001000]; int countW[1001000]; struct Cut_t { Cut_t() {}; Cut_t(int inPosX, long long inH, long long inD) : posX(inPosX), H(inH), D(inD) {} int posX; long long H; long long D; }; Cut_t CutTab[510000]; int lastCut = -1; int compr(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int cnt = 0; scanf("%i %i", &T, &K); for (int i = 0; i < T; i++) { scanf("%i", &W[i]); } W[T] = 1000001; for (int i = 0; i < K; i++) { scanf("%lld %lld", &D[i], &H[i]); } for (int i = 0; i <= 1000001; i++) { countW[0] = 0; } for (int i = 0; i <= T; i++) { countW[W[i]]++; } int w = 0; for (int i = 0; i <= 1000001; i++) { for (int j = 0; j < countW[i]; j++) { W[w] = i; w++; } } //qsort(W, T, sizeof(int), compr); sumW[T] = 0; for (int i = T - 1; i >= 0; i--) { sumW[i] = sumW[i + 1] + W[i]; } w = 0; for (int i = 0; i < 1000001; i++) { while (W[w] < i) { w++; } cutIdx[i] = w; } lastCut = 0; CutTab[lastCut] = Cut_t(0, 0, 0); for (int i = 0; i < K; i++) { long long res = 0; int posX = T; while (1) { Cut_t cut = CutTab[lastCut]; long long DD = D[i] - cut.D; long long diffH = H[i] - cut.H; if (cut.H + DD * W[cut.posX] >= H[i]) // CUT ALL { res += (sumW[cut.posX] - sumW[posX]) * DD - diffH * (posX - cut.posX); posX = cut.posX; lastCut--; if (lastCut == -1) { lastCut = 0; CutTab[lastCut] = Cut_t(posX, H[i], D[i]); break; } } else { long long idx = (diffH + (DD - 1)) / DD; if (idx >= 1000001) { break; } int newPosX = cutIdx[(diffH + (DD - 1)) / DD]; res += (sumW[newPosX] - sumW[posX]) * DD - diffH * (posX - newPosX); lastCut++; CutTab[lastCut] = Cut_t(newPosX, H[i], D[i]); break; } } printf("%lld\n", res); } return 0; }
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | #include "stdio.h" #include "stdlib.h" int T = 0; int K = 0; int W[510000]; long long sumW[510000]; long long D[510000]; long long H[510000]; int cutIdx[1001000]; int countW[1001000]; struct Cut_t { Cut_t() {}; Cut_t(int inPosX, long long inH, long long inD) : posX(inPosX), H(inH), D(inD) {} int posX; long long H; long long D; }; Cut_t CutTab[510000]; int lastCut = -1; int compr(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int cnt = 0; scanf("%i %i", &T, &K); for (int i = 0; i < T; i++) { scanf("%i", &W[i]); } W[T] = 1000001; for (int i = 0; i < K; i++) { scanf("%lld %lld", &D[i], &H[i]); } for (int i = 0; i <= 1000001; i++) { countW[0] = 0; } for (int i = 0; i <= T; i++) { countW[W[i]]++; } int w = 0; for (int i = 0; i <= 1000001; i++) { for (int j = 0; j < countW[i]; j++) { W[w] = i; w++; } } //qsort(W, T, sizeof(int), compr); sumW[T] = 0; for (int i = T - 1; i >= 0; i--) { sumW[i] = sumW[i + 1] + W[i]; } w = 0; for (int i = 0; i < 1000001; i++) { while (W[w] < i) { w++; } cutIdx[i] = w; } lastCut = 0; CutTab[lastCut] = Cut_t(0, 0, 0); for (int i = 0; i < K; i++) { long long res = 0; int posX = T; while (1) { Cut_t cut = CutTab[lastCut]; long long DD = D[i] - cut.D; long long diffH = H[i] - cut.H; if (cut.H + DD * W[cut.posX] >= H[i]) // CUT ALL { res += (sumW[cut.posX] - sumW[posX]) * DD - diffH * (posX - cut.posX); posX = cut.posX; lastCut--; if (lastCut == -1) { lastCut = 0; CutTab[lastCut] = Cut_t(posX, H[i], D[i]); break; } } else { long long idx = (diffH + (DD - 1)) / DD; if (idx >= 1000001) { break; } int newPosX = cutIdx[(diffH + (DD - 1)) / DD]; res += (sumW[newPosX] - sumW[posX]) * DD - diffH * (posX - newPosX); lastCut++; CutTab[lastCut] = Cut_t(newPosX, H[i], D[i]); break; } } printf("%lld\n", res); } return 0; } |