#include <iostream> #include <vector> #include <algorithm> int const MAX = 500009; int n, m; long long int field [MAX]; long long int dist [MAX]; int findFirstCutPos (long long int tab[], long long int val, long long int d){ int l = 0; int r = n-1; int pos; if (d*tab[r] <= val) return n; if (d*tab[l] >= val) return 0; while (r>l) { pos= (l+r)/2; if (d*tab[pos] >= val) r = pos; else if(l==pos) l=r; else l = pos; } return l; } int main() { int i, j, firstCutPos; long long int d, b; long long int sum=0, last=0, cur; std::cin >> n; std::cin >> m; i = n; while (i--) { std::cin >> j; field[i] = j; sum += j; } std::sort(field, field+n); dist[0] = field[0]; for( i = 1; i < n; i++ ) { dist[i] = dist[i-1]+field[i]; } while (m--) { std::cin >> d; std::cin >> b; cur = sum * d; firstCutPos = findFirstCutPos(field, b,d); if (firstCutPos-1 >= 0) cur -= d*dist[firstCutPos-1]; cur -= (n-firstCutPos) * b; if (cur < last) cur = last; std::cout << (cur-last) << std::endl; last = cur; } 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 | #include <iostream> #include <vector> #include <algorithm> int const MAX = 500009; int n, m; long long int field [MAX]; long long int dist [MAX]; int findFirstCutPos (long long int tab[], long long int val, long long int d){ int l = 0; int r = n-1; int pos; if (d*tab[r] <= val) return n; if (d*tab[l] >= val) return 0; while (r>l) { pos= (l+r)/2; if (d*tab[pos] >= val) r = pos; else if(l==pos) l=r; else l = pos; } return l; } int main() { int i, j, firstCutPos; long long int d, b; long long int sum=0, last=0, cur; std::cin >> n; std::cin >> m; i = n; while (i--) { std::cin >> j; field[i] = j; sum += j; } std::sort(field, field+n); dist[0] = field[0]; for( i = 1; i < n; i++ ) { dist[i] = dist[i-1]+field[i]; } while (m--) { std::cin >> d; std::cin >> b; cur = sum * d; firstCutPos = findFirstCutPos(field, b,d); if (firstCutPos-1 >= 0) cur -= d*dist[firstCutPos-1]; cur -= (n-firstCutPos) * b; if (cur < last) cur = last; std::cout << (cur-last) << std::endl; last = cur; } return 0; } |