#include <iostream> #include <algorithm> #include <cstdint> //#define uint64_t unsigned long long int using namespace std; uint64_t n, m; uint64_t a[500000]; uint64_t d; uint64_t b; uint64_t s[500001]; uint64_t wykos; typedef struct { uint64_t d, b, i; // day, level, index; } slope_t; slope_t sl[500001]; int sl_last = 0; int binarys(int imin, int imax, uint64_t b, uint64_t level, uint64_t days) { int imid; while (imax != imin) { imid = (imax + imin) / 2; if ( b >= level + days * a[imid] ) imin = imid + 1; else imax = imid; } return imin; } int main(int argc, char **argv) { cin >> n >> m; int i; for (i = 0; i < n; i++) cin >> a[i]; sort (a, &a[n]); s[0] = 0; for (i = 0; i < n; i++) s[i+1] = s[i] + a[i]; sl[0].d = 0; sl[0].b = 0; sl[0].i = 0; int imax, imin; int index; for (i = 0; i < m; i++) { cin >> d >> b; wykos = 0; imax = n; imin = sl[sl_last].i; while((d - sl[sl_last].d) * a[imin] + sl[sl_last].b > b) { wykos += (imax - imin) * (sl[sl_last].b - b); wykos += (s[imax] - s[imin]) * (d - sl[sl_last].d); sl_last--; if (sl_last == -1) break; imax = imin; imin = sl[sl_last].i; } if (sl_last != -1) { index = binarys(imin, imax, b, sl[sl_last].b, d - sl[sl_last].d); wykos += (imax - index) * (sl[sl_last].b - b); wykos += (s[imax] - s[index]) * (d - sl[sl_last].d); } else index = 0; cout << wykos << endl; if (index != n) { sl_last ++ ; sl[sl_last].d = d; sl[sl_last].b = b; sl[sl_last].i = index; } } 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 | #include <iostream> #include <algorithm> #include <cstdint> //#define uint64_t unsigned long long int using namespace std; uint64_t n, m; uint64_t a[500000]; uint64_t d; uint64_t b; uint64_t s[500001]; uint64_t wykos; typedef struct { uint64_t d, b, i; // day, level, index; } slope_t; slope_t sl[500001]; int sl_last = 0; int binarys(int imin, int imax, uint64_t b, uint64_t level, uint64_t days) { int imid; while (imax != imin) { imid = (imax + imin) / 2; if ( b >= level + days * a[imid] ) imin = imid + 1; else imax = imid; } return imin; } int main(int argc, char **argv) { cin >> n >> m; int i; for (i = 0; i < n; i++) cin >> a[i]; sort (a, &a[n]); s[0] = 0; for (i = 0; i < n; i++) s[i+1] = s[i] + a[i]; sl[0].d = 0; sl[0].b = 0; sl[0].i = 0; int imax, imin; int index; for (i = 0; i < m; i++) { cin >> d >> b; wykos = 0; imax = n; imin = sl[sl_last].i; while((d - sl[sl_last].d) * a[imin] + sl[sl_last].b > b) { wykos += (imax - imin) * (sl[sl_last].b - b); wykos += (s[imax] - s[imin]) * (d - sl[sl_last].d); sl_last--; if (sl_last == -1) break; imax = imin; imin = sl[sl_last].i; } if (sl_last != -1) { index = binarys(imin, imax, b, sl[sl_last].b, d - sl[sl_last].d); wykos += (imax - index) * (sl[sl_last].b - b); wykos += (s[imax] - s[index]) * (d - sl[sl_last].d); } else index = 0; cout << wykos << endl; if (index != n) { sl_last ++ ; sl[sl_last].d = d; sl[sl_last].b = b; sl[sl_last].i = index; } } return 0; } |