#include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; struct mh_t{ int pos; long long height; long long day; bool operator<(const mh_t& that) const { return (pos < that.pos); } mh_t(int p, long long h, long long d) : pos(p), height(h), day(d) {} }; vector<int> aSorted; vector<long long> sums; set<mh_t> mowings; static inline void calculateSums(int n) { long long sum = 0; for (int i = 0; i < n; ++i) { sum += aSorted[i]; sums.push_back(sum); } } static inline int findPos(long long d, long long b) { int pos = -1; int z = aSorted.size() - 1; int a = 0; mh_t searchKey(a, b, d); set<mh_t>::iterator it; long long height; searchKey.pos = z; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height >= b) { return z; } searchKey.pos = a; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height <= b) { return -1; } while (z - a > 1) { searchKey.pos = (z + a) / 2; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height >= b) { a = searchKey.pos; } else { z = searchKey.pos; } } return a; } static long long process(long long d, long long b) { long long result = 0; int pos = findPos(d, b); if (pos >= 0) { int previous = -1; for (set<mh_t>::iterator it = mowings.begin(); it != mowings.end(); ++it) { if (it->pos <= pos) { result += (sums[it->pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (it->pos - previous); } else { if (previous < pos) { result += (sums[pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (pos - previous); } mowings.erase(mowings.begin(), it); break; } previous = it->pos; } mowings.insert(mh_t(pos, b, d)); } return result; } int main() { int n, m; long long d, b; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { int a; scanf("%d", &a); aSorted.push_back(a); } sort(aSorted.begin(), aSorted.end(), greater<int>()); calculateSums(n); mowings.insert(mh_t(n, 0, 0)); while (m--) { scanf("%lld %lld", &d, &b); printf("%lld\n", process(d, b)); } 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 | #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; struct mh_t{ int pos; long long height; long long day; bool operator<(const mh_t& that) const { return (pos < that.pos); } mh_t(int p, long long h, long long d) : pos(p), height(h), day(d) {} }; vector<int> aSorted; vector<long long> sums; set<mh_t> mowings; static inline void calculateSums(int n) { long long sum = 0; for (int i = 0; i < n; ++i) { sum += aSorted[i]; sums.push_back(sum); } } static inline int findPos(long long d, long long b) { int pos = -1; int z = aSorted.size() - 1; int a = 0; mh_t searchKey(a, b, d); set<mh_t>::iterator it; long long height; searchKey.pos = z; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height >= b) { return z; } searchKey.pos = a; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height <= b) { return -1; } while (z - a > 1) { searchKey.pos = (z + a) / 2; it = mowings.lower_bound(searchKey); height = it->height + aSorted[searchKey.pos] * (d - it->day); if (height >= b) { a = searchKey.pos; } else { z = searchKey.pos; } } return a; } static long long process(long long d, long long b) { long long result = 0; int pos = findPos(d, b); if (pos >= 0) { int previous = -1; for (set<mh_t>::iterator it = mowings.begin(); it != mowings.end(); ++it) { if (it->pos <= pos) { result += (sums[it->pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (it->pos - previous); } else { if (previous < pos) { result += (sums[pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (pos - previous); } mowings.erase(mowings.begin(), it); break; } previous = it->pos; } mowings.insert(mh_t(pos, b, d)); } return result; } int main() { int n, m; long long d, b; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { int a; scanf("%d", &a); aSorted.push_back(a); } sort(aSorted.begin(), aSorted.end(), greater<int>()); calculateSums(n); mowings.insert(mh_t(n, 0, 0)); while (m--) { scanf("%lld %lld", &d, &b); printf("%lld\n", process(d, b)); } return 0; } |