#include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <utility> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <unordered_set> #include <unordered_map> #define VAR(i,v) __typeof(v) i = (v) #define SIZE(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define REP(i,b) for(int i=0; i<(b); ++i) #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORD(i,a,b) for(int i=(a); i>=(b); --i) #define FOREACH(i,c) for(VAR(i,(c).begin()); i != (c).end(); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second #define NL printf("\n") using namespace std; typedef pair<int,int> PII; typedef vector<int> VI; typedef unsigned long long LL; const int INF = 2147483640; const int MAXN = 500005; const LL MAXB = 500000000; LL a[MAXN], c[MAXN]; LL s[MAXN]; LL level; LL prv; int n, m; LL get_profit1(LL day, LL h) { FOR(i,1,n) c[i] += a[i]*(day-prv); LL res = 0; FOR(i,1,n) if(c[i] >= h) { res += c[i] - h; c[i] = h; } return res; } LL get_profit2(LL day, LL h) { int lo = 1, hi = n; int pos = 0; while(lo <= hi) { int mid = lo + (hi-lo)/2; if(a[mid]*(day-prv)+level < h) { pos = mid; lo = mid + 1; } else { hi = mid - 1; } } LL res = s[n]*(day-prv) - (s[pos]*(day-prv)) + level*n - h*(n-pos); return res; } int main() { scanf("%d %d", &n, &m); FOR(i,1,n) scanf("%lld", &a[i]); sort(a+1, a+n+1); FOR(i,1,n) s[i] = s[i-1] + a[i]; if(LL(n)*LL(max(n,m)) <= MAXB) { REP(i,m) { LL d, b; scanf("%lld %lld", &d, &b); LL q = get_profit1(d,b); printf("%lld\n", q); prv = d; } } else { REP(i,m) { LL d, b; scanf("%lld %lld", &d, &b); LL q = get_profit2(d,b); printf("%lld\n", q); level = b; prv = d; } } 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 | #include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <utility> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <unordered_set> #include <unordered_map> #define VAR(i,v) __typeof(v) i = (v) #define SIZE(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define REP(i,b) for(int i=0; i<(b); ++i) #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORD(i,a,b) for(int i=(a); i>=(b); --i) #define FOREACH(i,c) for(VAR(i,(c).begin()); i != (c).end(); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second #define NL printf("\n") using namespace std; typedef pair<int,int> PII; typedef vector<int> VI; typedef unsigned long long LL; const int INF = 2147483640; const int MAXN = 500005; const LL MAXB = 500000000; LL a[MAXN], c[MAXN]; LL s[MAXN]; LL level; LL prv; int n, m; LL get_profit1(LL day, LL h) { FOR(i,1,n) c[i] += a[i]*(day-prv); LL res = 0; FOR(i,1,n) if(c[i] >= h) { res += c[i] - h; c[i] = h; } return res; } LL get_profit2(LL day, LL h) { int lo = 1, hi = n; int pos = 0; while(lo <= hi) { int mid = lo + (hi-lo)/2; if(a[mid]*(day-prv)+level < h) { pos = mid; lo = mid + 1; } else { hi = mid - 1; } } LL res = s[n]*(day-prv) - (s[pos]*(day-prv)) + level*n - h*(n-pos); return res; } int main() { scanf("%d %d", &n, &m); FOR(i,1,n) scanf("%lld", &a[i]); sort(a+1, a+n+1); FOR(i,1,n) s[i] = s[i-1] + a[i]; if(LL(n)*LL(max(n,m)) <= MAXB) { REP(i,m) { LL d, b; scanf("%lld %lld", &d, &b); LL q = get_profit1(d,b); printf("%lld\n", q); prv = d; } } else { REP(i,m) { LL d, b; scanf("%lld %lld", &d, &b); LL q = get_profit2(d,b); printf("%lld\n", q); level = b; prv = d; } } return 0; } |