// Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #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 MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; #define suma(i, j) (sum[i] - sum[j+1]) int n, m; long long d, b; long long tab[1000007]; long long sum[1000007]; struct trawa { long long poz; long long d; long long wys; }; stack <trawa> stos; trawa t; int main() { scanf("%d %d", &n, &m); forr(i, n) { scanf("%lld", &tab[i]); } sort(tab, tab+n); FORD(i, n-1, 0) sum[i] = sum[i+1] + tab[i]; t.poz = t.d = t.wys = 0; stos.push(t); forr(i, m) { scanf("%lld %lld", &d, &b); long long last_poz = n; long long res = 0; while(!stos.empty()) { t = stos.top(); //cout << " bada odcinek od " << t.poz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl; long long wys_poz = t.wys + (d - t.d)*tab[t.poz]; if(wys_poz < b) break; stos.pop(); res += suma(t.poz, last_poz-1)*(d - t.d) - (last_poz - t.poz)*(b-t.wys); //cout << " wszedl caly, res = " << res << endl; last_poz = t.poz; } long long pocz = 0, kon, s; if(!stos.empty()) { pocz = t.poz; kon = last_poz; while(pocz != kon) { s = (pocz + kon) >> 1; if(t.wys + tab[s]*(d - t.d) < b) pocz = s+1; else kon = s; } //cout << " lb znalazl " << pocz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl; res += suma(pocz, last_poz-1)*(d - t.d) - (last_poz - pocz)*(b-t.wys); } if(pocz < n) { t.d = d; t.wys = b; t.poz = pocz; stos.push(t); } printf("%lld\n", res); } 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 | // Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #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 MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; #define suma(i, j) (sum[i] - sum[j+1]) int n, m; long long d, b; long long tab[1000007]; long long sum[1000007]; struct trawa { long long poz; long long d; long long wys; }; stack <trawa> stos; trawa t; int main() { scanf("%d %d", &n, &m); forr(i, n) { scanf("%lld", &tab[i]); } sort(tab, tab+n); FORD(i, n-1, 0) sum[i] = sum[i+1] + tab[i]; t.poz = t.d = t.wys = 0; stos.push(t); forr(i, m) { scanf("%lld %lld", &d, &b); long long last_poz = n; long long res = 0; while(!stos.empty()) { t = stos.top(); //cout << " bada odcinek od " << t.poz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl; long long wys_poz = t.wys + (d - t.d)*tab[t.poz]; if(wys_poz < b) break; stos.pop(); res += suma(t.poz, last_poz-1)*(d - t.d) - (last_poz - t.poz)*(b-t.wys); //cout << " wszedl caly, res = " << res << endl; last_poz = t.poz; } long long pocz = 0, kon, s; if(!stos.empty()) { pocz = t.poz; kon = last_poz; while(pocz != kon) { s = (pocz + kon) >> 1; if(t.wys + tab[s]*(d - t.d) < b) pocz = s+1; else kon = s; } //cout << " lb znalazl " << pocz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl; res += suma(pocz, last_poz-1)*(d - t.d) - (last_poz - pocz)*(b-t.wys); } if(pocz < n) { t.d = d; t.wys = b; t.poz = pocz; stos.push(t); } printf("%lld\n", res); } return 0; } |