#define NDEBUG #include <map> #include <vector> #include <algorithm> #include <cassert> class Height { long long h; public: explicit Height(long long h) : h(h) { } long long getH() const { return h; } }; class cut_finder_comp { const std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> >&M; const std::vector<long long> &A; const long long d; public: cut_finder_comp(const std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> > &M, const std::vector<long long> &A, long long d) : M(M), A(A), d(d) { } bool operator()(Height b, long long idx) const { auto I = M.upper_bound(idx); assert(I != M.begin()); --I; long long prevH = I->second.first; long long prevD = I->second.second; long long a = A[idx]; long long nowH = (d - prevD) * a + prevH; // fprintf(stderr,"< ret %lld < %lld\n\n", nowH, b.getH()); return nowH > b.getH(); } }; int main() { int n, m; scanf("%d%d", &n, &m); std::vector<long long> A(n); std::vector<long long> R(n); std::vector<long long> Sum(n); for (int i = 0; i < n; ++i) { R[i] = i; } for (int i = 0; i < n; ++i) { scanf("%lld", &A[i]); } std::sort(A.begin(), A.end()); long long TotalSum = 0; for (int i = 0; i < n; ++i) { Sum[i] = TotalSum; TotalSum += A[i]; } std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> > M; M[0] = std::make_pair(0, 0); while (m--) { long long d, b; scanf("%lld%lld", &d, &b); auto I = std::upper_bound(R.begin(), R.end(), Height(b), cut_finder_comp(M, A, d)); if (I == R.end()) { // we cut so high, it doesn't matter for anyone.. printf("0\n"); continue; } long long idx = *I; // fprintf(stderr,"< find idx = %lld\n", idx); auto MI = M.upper_bound(idx); assert(MI != M.begin()); --MI; long long res = 0; long long prevB = MI->second.first; // cm long long prevD = MI->second.second; // day long long prevIdx = idx; auto Next = ++MI; // fprintf(stderr,"< prevB = %lld\n", prevB); // fprintf(stderr,"< prevD = %lld\n", prevD); // fprintf(stderr,"< prevIdx = %lld\n", prevIdx); while (Next != M.end()) { MI = Next; long long currIdx = MI->first; long long days = d - prevD; long long sumA = Sum[prevIdx]; long long sumB = Sum[currIdx]; assert(sumB > sumA); //assert(b >= prevB); long long growPerDay = sumB - sumA; res += (days * growPerDay) - (currIdx - prevIdx) * (b - prevB); prevB = MI->second.first; prevD = MI->second.second; prevIdx = currIdx; ++Next; M.erase(MI); } { // fprintf(stderr,"< totalSum = %lld\n", TotalSum); // fprintf(stderr,"< Sum[prevIdx] = %lld\n", Sum[prevIdx]); long long growPerDay = TotalSum - Sum[prevIdx]; long long days = d - prevD; // fprintf(stderr,"< (%lld * %lld) - (%lld - %lld) * %lld\n", // (int)days, (int)growPerDay, (int)n, prevIdx, (int)b); res += (days * growPerDay) - (n - prevIdx) * (b - prevB); } M[idx] = std::make_pair(b, d); printf("%lld\n", res); } }
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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | #define NDEBUG #include <map> #include <vector> #include <algorithm> #include <cassert> class Height { long long h; public: explicit Height(long long h) : h(h) { } long long getH() const { return h; } }; class cut_finder_comp { const std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> >&M; const std::vector<long long> &A; const long long d; public: cut_finder_comp(const std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> > &M, const std::vector<long long> &A, long long d) : M(M), A(A), d(d) { } bool operator()(Height b, long long idx) const { auto I = M.upper_bound(idx); assert(I != M.begin()); --I; long long prevH = I->second.first; long long prevD = I->second.second; long long a = A[idx]; long long nowH = (d - prevD) * a + prevH; // fprintf(stderr,"< ret %lld < %lld\n\n", nowH, b.getH()); return nowH > b.getH(); } }; int main() { int n, m; scanf("%d%d", &n, &m); std::vector<long long> A(n); std::vector<long long> R(n); std::vector<long long> Sum(n); for (int i = 0; i < n; ++i) { R[i] = i; } for (int i = 0; i < n; ++i) { scanf("%lld", &A[i]); } std::sort(A.begin(), A.end()); long long TotalSum = 0; for (int i = 0; i < n; ++i) { Sum[i] = TotalSum; TotalSum += A[i]; } std::map</*idx*/long long, std::pair</*height*/ long long, /*time*/ long long> > M; M[0] = std::make_pair(0, 0); while (m--) { long long d, b; scanf("%lld%lld", &d, &b); auto I = std::upper_bound(R.begin(), R.end(), Height(b), cut_finder_comp(M, A, d)); if (I == R.end()) { // we cut so high, it doesn't matter for anyone.. printf("0\n"); continue; } long long idx = *I; // fprintf(stderr,"< find idx = %lld\n", idx); auto MI = M.upper_bound(idx); assert(MI != M.begin()); --MI; long long res = 0; long long prevB = MI->second.first; // cm long long prevD = MI->second.second; // day long long prevIdx = idx; auto Next = ++MI; // fprintf(stderr,"< prevB = %lld\n", prevB); // fprintf(stderr,"< prevD = %lld\n", prevD); // fprintf(stderr,"< prevIdx = %lld\n", prevIdx); while (Next != M.end()) { MI = Next; long long currIdx = MI->first; long long days = d - prevD; long long sumA = Sum[prevIdx]; long long sumB = Sum[currIdx]; assert(sumB > sumA); //assert(b >= prevB); long long growPerDay = sumB - sumA; res += (days * growPerDay) - (currIdx - prevIdx) * (b - prevB); prevB = MI->second.first; prevD = MI->second.second; prevIdx = currIdx; ++Next; M.erase(MI); } { // fprintf(stderr,"< totalSum = %lld\n", TotalSum); // fprintf(stderr,"< Sum[prevIdx] = %lld\n", Sum[prevIdx]); long long growPerDay = TotalSum - Sum[prevIdx]; long long days = d - prevD; // fprintf(stderr,"< (%lld * %lld) - (%lld - %lld) * %lld\n", // (int)days, (int)growPerDay, (int)n, prevIdx, (int)b); res += (days * growPerDay) - (n - prevIdx) * (b - prevB); } M[idx] = std::make_pair(b, d); printf("%lld\n", res); } } |