#include <cstdio> #include <algorithm> using namespace std; #define nmax 500000 int n, m; int a[nmax]; long long aktualizacja[nmax], trawa[nmax]; long long stan(int i, long long d) { trawa[i] += (d - aktualizacja[i]) * a[i]; aktualizacja[i] = d; return trawa[i]; } int szukaj(long long t, long long d) { int b = 0, e = n-1, s; while (b+1 < e-1) { s = (e+b) / 2; if (stan(s, d) > t) { e = s-1; } else { b = s+1; } } s = e; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; return s; } int main() { scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { scanf("%d", &a[i]); trawa[i] = 0; aktualizacja[i] = 0; } sort(a, a+n); long long d, b, res; int s; for (int i=0; i<m; i++) { scanf("%lld %lld", &d, &b); s = szukaj(b, d); res = 0; while (s < n) { if (stan(s, d) > b) { res += stan(s, d) - b; trawa[s] = b; } s++; } 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 | #include <cstdio> #include <algorithm> using namespace std; #define nmax 500000 int n, m; int a[nmax]; long long aktualizacja[nmax], trawa[nmax]; long long stan(int i, long long d) { trawa[i] += (d - aktualizacja[i]) * a[i]; aktualizacja[i] = d; return trawa[i]; } int szukaj(long long t, long long d) { int b = 0, e = n-1, s; while (b+1 < e-1) { s = (e+b) / 2; if (stan(s, d) > t) { e = s-1; } else { b = s+1; } } s = e; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) <= t && s < n-1) s++; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; if (stan(s,d) > t && s > 0 && stan(s-1,d) > t) s--; return s; } int main() { scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { scanf("%d", &a[i]); trawa[i] = 0; aktualizacja[i] = 0; } sort(a, a+n); long long d, b, res; int s; for (int i=0; i<m; i++) { scanf("%lld %lld", &d, &b); s = szukaj(b, d); res = 0; while (s < n) { if (stan(s, d) > b) { res += stan(s, d) - b; trawa[s] = b; } s++; } printf("%lld\n", res); } return 0; } |