#include <cstdio> #include <algorithm> #include <functional> using namespace std; const int offset = 1 << 19; typedef long long ll; pair<ll, ll> mini[offset << 1]; pair<ll, ll> total[offset << 1]; ll last[offset << 1]; pair<ll, ll> lastcut[offset << 1]; inline void updateTime(int v, ll time) { total[v].first += total[v].second * (time - last[v]); mini[v].first += mini[v].second * (time - last[v]); last[v] = time; } ll cut(int v, int size, ll time, ll b) { updateTime(v, time); ll ans = total[v].first - b * size; total[v].first = b * size; mini[v].first = b; lastcut[v] = make_pair(b, time); return ans; } ll update(int v, int size, ll time, ll b) { if(size == 1) { if(mini[v].first >= b) return cut(v, size, time, b); return 0; } if(lastcut[v].second) { cut(v * 2, size / 2, lastcut[v].second, lastcut[v].first); cut(v * 2 + 1, size / 2, lastcut[v].second, lastcut[v].first); lastcut[v].second = 0; } updateTime(v * 2, time); updateTime(v * 2 + 1, time); long long ans; if(mini[v * 2].first >= b) ans = cut(v * 2, size / 2, time, b) + update(v * 2 + 1, size / 2, time, b); else ans = update(v * 2, size / 2, time, b); total[v].first = total[v * 2].first + total[v * 2 + 1].first; mini[v].first = mini[v * 2 + 1].first; last[v] = time; return ans; } int a[500000]; int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) scanf("%d", a + i); sort(a, a + n, greater<int>()); for(int i = 0; i < n; i++) mini[i + offset].second = total[i+offset].second = a[i]; for(int i = offset - 1; i > 0; i--) { mini[i].second = mini[i * 2 + 1].second; total[i].second = total[i * 2].second + total[i * 2 + 1].second; } while(m--) { ll d, b; scanf("%lld %lld", &d, &b); printf("%lld\n", update(1, offset, d, b)); } }
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 | #include <cstdio> #include <algorithm> #include <functional> using namespace std; const int offset = 1 << 19; typedef long long ll; pair<ll, ll> mini[offset << 1]; pair<ll, ll> total[offset << 1]; ll last[offset << 1]; pair<ll, ll> lastcut[offset << 1]; inline void updateTime(int v, ll time) { total[v].first += total[v].second * (time - last[v]); mini[v].first += mini[v].second * (time - last[v]); last[v] = time; } ll cut(int v, int size, ll time, ll b) { updateTime(v, time); ll ans = total[v].first - b * size; total[v].first = b * size; mini[v].first = b; lastcut[v] = make_pair(b, time); return ans; } ll update(int v, int size, ll time, ll b) { if(size == 1) { if(mini[v].first >= b) return cut(v, size, time, b); return 0; } if(lastcut[v].second) { cut(v * 2, size / 2, lastcut[v].second, lastcut[v].first); cut(v * 2 + 1, size / 2, lastcut[v].second, lastcut[v].first); lastcut[v].second = 0; } updateTime(v * 2, time); updateTime(v * 2 + 1, time); long long ans; if(mini[v * 2].first >= b) ans = cut(v * 2, size / 2, time, b) + update(v * 2 + 1, size / 2, time, b); else ans = update(v * 2, size / 2, time, b); total[v].first = total[v * 2].first + total[v * 2 + 1].first; mini[v].first = mini[v * 2 + 1].first; last[v] = time; return ans; } int a[500000]; int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) scanf("%d", a + i); sort(a, a + n, greater<int>()); for(int i = 0; i < n; i++) mini[i + offset].second = total[i+offset].second = a[i]; for(int i = offset - 1; i > 0; i--) { mini[i].second = mini[i * 2 + 1].second; total[i].second = total[i * 2].second + total[i * 2 + 1].second; } while(m--) { ll d, b; scanf("%lld %lld", &d, &b); printf("%lld\n", update(1, offset, d, b)); } } |