#include <cassert> #include <cstdio> #include <algorithm> #define MAXN 500007 #define MAXM 500007 using namespace std; //#define DEBUG #ifdef DEBUG #define ASSERT(x) assert(x) #else #define ASSERT(X) #endif typedef long long slng; int N, M; int a[MAXN]; slng suma[MAXN+1]; // [i] = on day d[i] cut to b[i] starting from a[ind[i]]. // d[i] ascending, b[i] ascending, ind[i] ascending. slng numd, d[MAXM], b[MAXM], ind[MAXM]; // find lowest affected d. int findd(slng di, slng bi) { int l = 0, r = numd; while (l != r) { int s = (l+r)/2; slng ah = (s != numd-1) ? a[ind[s+1] - 1] : a[N-1]; if (b[s] + (di - d[s]) * ah <= bi /* not affected by cutting at bi */) { l = s+1; } else /* affected by cutting at bi. */ { r = s; } } return l; } // find lowest affected a. int finda(int dd, slng di, slng bi) { int l, r, initr; l = ind[dd]; initr = r = (dd < numd-1) ? ind[dd+1] : N; while (l != r) { int s = (l+r)/2; if (b[dd] + (di - d[dd]) * (slng) a[s] <= bi /* not affected by cutting at bi */) { l = s+1; } else /* affected by cutting at bi. */ { r = s; } } ASSERT(l != initr); ASSERT(b[dd] + (di - d[dd]) * (slng) a[l] >= bi); return l; } slng cut(int dd, int aa, slng di, slng bi) { slng ret = 0; int i; int ar; ar = (dd < numd-1) ? ind[dd+1] : N; ret += (b[dd] - bi /* <= 0 here*/) * (slng)(ar - aa); ret += (di - d[dd]) * (suma[ar] - suma[aa]); #ifdef DEBUG printf("ret=%lld", ret); #endif for (i = dd+1; i < numd; i++) { ar = (i < numd-1) ? ind[i+1] : N; ret += (b[i] - bi) * (slng)(ar - ind[i]); ret += (di - d[i]) * (suma[ar] - suma[ind[i]]); #ifdef DEBUG printf(" %lld", ret); #endif } #ifdef DEBUG printf("\n"); #endif return ret; } int main() { int i; #ifdef DEBUG int j; #endif scanf("%d%d", &N, &M); for (i = 0; i < N; i++) scanf("%d", &a[i]); // sort and partial sums. sort(a, a+N); // suma[N] = sum(a,[0,N-1]) suma[0] = 0; for (i = 1; i <= N; i++) suma[i] = suma[i-1] + a[i-1]; // everything cut at 0 on the 0th day. numd = 1; d[0] = 0; b[0] = 0; ind[0] = 0; for (i = 0; i < M; i++) { slng di, bi; int dd, aa; scanf("%lld%lld", &di, &bi); #ifdef DEBUG printf("di=%lld bi=%lld\n", di, bi); for (j = 0; j < numd; j++) { printf("(d=%lld b=%lld a[ind=%lld]=%d) ", d[j], b[j], ind[j], a[ind[j]]); } printf("\n"); #endif dd = findd(di, bi); if (dd == numd) { printf("0\n"); continue; } aa = finda(dd, di, bi); ASSERT(bi > b[dd] || aa == ind[dd]); #ifdef DEBUG printf("dd=%d aa=%d\n", dd, aa); #endif printf("%lld\n", cut(dd, aa, di, bi)); if (aa == ind[dd]) dd--; // overwrite d[dd+1] = di; b[dd+1] = bi; ind[dd+1] = aa; numd = dd+2; } 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 | #include <cassert> #include <cstdio> #include <algorithm> #define MAXN 500007 #define MAXM 500007 using namespace std; //#define DEBUG #ifdef DEBUG #define ASSERT(x) assert(x) #else #define ASSERT(X) #endif typedef long long slng; int N, M; int a[MAXN]; slng suma[MAXN+1]; // [i] = on day d[i] cut to b[i] starting from a[ind[i]]. // d[i] ascending, b[i] ascending, ind[i] ascending. slng numd, d[MAXM], b[MAXM], ind[MAXM]; // find lowest affected d. int findd(slng di, slng bi) { int l = 0, r = numd; while (l != r) { int s = (l+r)/2; slng ah = (s != numd-1) ? a[ind[s+1] - 1] : a[N-1]; if (b[s] + (di - d[s]) * ah <= bi /* not affected by cutting at bi */) { l = s+1; } else /* affected by cutting at bi. */ { r = s; } } return l; } // find lowest affected a. int finda(int dd, slng di, slng bi) { int l, r, initr; l = ind[dd]; initr = r = (dd < numd-1) ? ind[dd+1] : N; while (l != r) { int s = (l+r)/2; if (b[dd] + (di - d[dd]) * (slng) a[s] <= bi /* not affected by cutting at bi */) { l = s+1; } else /* affected by cutting at bi. */ { r = s; } } ASSERT(l != initr); ASSERT(b[dd] + (di - d[dd]) * (slng) a[l] >= bi); return l; } slng cut(int dd, int aa, slng di, slng bi) { slng ret = 0; int i; int ar; ar = (dd < numd-1) ? ind[dd+1] : N; ret += (b[dd] - bi /* <= 0 here*/) * (slng)(ar - aa); ret += (di - d[dd]) * (suma[ar] - suma[aa]); #ifdef DEBUG printf("ret=%lld", ret); #endif for (i = dd+1; i < numd; i++) { ar = (i < numd-1) ? ind[i+1] : N; ret += (b[i] - bi) * (slng)(ar - ind[i]); ret += (di - d[i]) * (suma[ar] - suma[ind[i]]); #ifdef DEBUG printf(" %lld", ret); #endif } #ifdef DEBUG printf("\n"); #endif return ret; } int main() { int i; #ifdef DEBUG int j; #endif scanf("%d%d", &N, &M); for (i = 0; i < N; i++) scanf("%d", &a[i]); // sort and partial sums. sort(a, a+N); // suma[N] = sum(a,[0,N-1]) suma[0] = 0; for (i = 1; i <= N; i++) suma[i] = suma[i-1] + a[i-1]; // everything cut at 0 on the 0th day. numd = 1; d[0] = 0; b[0] = 0; ind[0] = 0; for (i = 0; i < M; i++) { slng di, bi; int dd, aa; scanf("%lld%lld", &di, &bi); #ifdef DEBUG printf("di=%lld bi=%lld\n", di, bi); for (j = 0; j < numd; j++) { printf("(d=%lld b=%lld a[ind=%lld]=%d) ", d[j], b[j], ind[j], a[ind[j]]); } printf("\n"); #endif dd = findd(di, bi); if (dd == numd) { printf("0\n"); continue; } aa = finda(dd, di, bi); ASSERT(bi > b[dd] || aa == ind[dd]); #ifdef DEBUG printf("dd=%d aa=%d\n", dd, aa); #endif printf("%lld\n", cut(dd, aa, di, bi)); if (aa == ind[dd]) dd--; // overwrite d[dd+1] = di; b[dd+1] = bi; ind[dd+1] = aa; numd = dd+2; } return 0; } |