#include<bits/stdc++.h> #define ll long long using namespace std; const ll N = 1e6; ll a, b, m, n, d, D, S, W, DNI; ll rosn [N], t [N]; ll read(ll x) { ll res = 0; for(;x>0;x-=(x&-x))res+=t[x]; return res; } ll zapytaj (ll a) { return read(a) - read(a-1); } void update(ll x ,ll w ) { for(;x<N;x+=(x&-x))t[x]+=w; } void rosnie (ll Q) { ll wart; for(ll i=1; i<=m; ++i) { wart = Q * rosn[i]; update(i, wart); } } void kosi (ll Q, ll b) { for(ll i=1; i <=m; ++i ) { ll wart = zapytaj(i); if(wart > b) { update(i, b-wart); S += (wart - b); } } } int main() { scanf("%lld %lld", &m, &n); for(ll i = 1; i <= m; ++i) { scanf("%lld", &W); rosn[i] = W; } for(ll i = 0; i < n; ++i) { scanf("%lld %lld", &d, &b); DNI = d-D; rosnie (DNI); kosi (DNI, b); D = d; printf("%lld\n", S); S = 0; } 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 | #include<bits/stdc++.h> #define ll long long using namespace std; const ll N = 1e6; ll a, b, m, n, d, D, S, W, DNI; ll rosn [N], t [N]; ll read(ll x) { ll res = 0; for(;x>0;x-=(x&-x))res+=t[x]; return res; } ll zapytaj (ll a) { return read(a) - read(a-1); } void update(ll x ,ll w ) { for(;x<N;x+=(x&-x))t[x]+=w; } void rosnie (ll Q) { ll wart; for(ll i=1; i<=m; ++i) { wart = Q * rosn[i]; update(i, wart); } } void kosi (ll Q, ll b) { for(ll i=1; i <=m; ++i ) { ll wart = zapytaj(i); if(wart > b) { update(i, b-wart); S += (wart - b); } } } int main() { scanf("%lld %lld", &m, &n); for(ll i = 1; i <= m; ++i) { scanf("%lld", &W); rosn[i] = W; } for(ll i = 0; i < n; ++i) { scanf("%lld %lld", &d, &b); DNI = d-D; rosnie (DNI); kosi (DNI, b); D = d; printf("%lld\n", S); S = 0; } return 0; } |