#include <bits/stdc++.h> using namespace std; int n, m; long long tab[500007]; long long czas[500007]; long long poz[500007]; int pocz[500007]; int kon[500007]; vector <int> wek; long long wyn; int bsa, bsb, bss; int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf("%lld", &tab[i]); } sort(tab+1, tab+1+n); for (int i=1; i<=n; i++) { tab[i]+=tab[i-1]; } pocz[0]=1; kon[0]=n; wek.push_back(0); for (int i=1; i<=m; i++) { scanf("%lld%lld", &czas[i], &poz[i]); wyn=0; while(!wek.empty()) { if ( ( czas[i] - czas[wek.back()] ) * ( tab[pocz[wek.back()]] - tab[pocz[wek.back()]-1] ) + poz[wek.back()] >= poz[i] ) { wyn+=( czas[i]-czas[wek.back()] ) * ( tab[kon[wek.back()]]-tab[pocz[wek.back()]-1] ) + ( kon[wek.back()]-pocz[wek.back()]+1 ) * ( poz[wek.back()]-poz[i] ); wek.pop_back(); } else { break; } } if (!wek.empty() && ( czas[i] - czas[wek.back()] ) * ( tab[kon[wek.back()]] - tab[kon[wek.back()]-1] ) + poz[wek.back()] >= poz[i] ) { bsa=pocz[wek.back()]; bsb=kon[wek.back()]; while(bsa<bsb) { bss=(bsa+bsb)>>1; if (( czas[i] - czas[wek.back()] ) * ( tab[bss] - tab[bss-1] ) + poz[wek.back()] >= poz[i]) { bsb=bss; } else { bsa=bss+1; } } wyn+=( czas[i]-czas[wek.back()] ) * ( tab[kon[wek.back()]]-tab[bsa-1] ) + ( kon[wek.back()]-bsa+1 ) * ( poz[wek.back()]-poz[i] ); kon[wek.back()]=bsa-1; } if (wek.empty()) { pocz[i]=1; kon[i]=n; wek.push_back(i); } else { if (kon[wek.back()]<n) { pocz[i]=kon[wek.back()]+1; kon[i]=n; wek.push_back(i); } } printf("%lld\n", wyn); } 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 | #include <bits/stdc++.h> using namespace std; int n, m; long long tab[500007]; long long czas[500007]; long long poz[500007]; int pocz[500007]; int kon[500007]; vector <int> wek; long long wyn; int bsa, bsb, bss; int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf("%lld", &tab[i]); } sort(tab+1, tab+1+n); for (int i=1; i<=n; i++) { tab[i]+=tab[i-1]; } pocz[0]=1; kon[0]=n; wek.push_back(0); for (int i=1; i<=m; i++) { scanf("%lld%lld", &czas[i], &poz[i]); wyn=0; while(!wek.empty()) { if ( ( czas[i] - czas[wek.back()] ) * ( tab[pocz[wek.back()]] - tab[pocz[wek.back()]-1] ) + poz[wek.back()] >= poz[i] ) { wyn+=( czas[i]-czas[wek.back()] ) * ( tab[kon[wek.back()]]-tab[pocz[wek.back()]-1] ) + ( kon[wek.back()]-pocz[wek.back()]+1 ) * ( poz[wek.back()]-poz[i] ); wek.pop_back(); } else { break; } } if (!wek.empty() && ( czas[i] - czas[wek.back()] ) * ( tab[kon[wek.back()]] - tab[kon[wek.back()]-1] ) + poz[wek.back()] >= poz[i] ) { bsa=pocz[wek.back()]; bsb=kon[wek.back()]; while(bsa<bsb) { bss=(bsa+bsb)>>1; if (( czas[i] - czas[wek.back()] ) * ( tab[bss] - tab[bss-1] ) + poz[wek.back()] >= poz[i]) { bsb=bss; } else { bsa=bss+1; } } wyn+=( czas[i]-czas[wek.back()] ) * ( tab[kon[wek.back()]]-tab[bsa-1] ) + ( kon[wek.back()]-bsa+1 ) * ( poz[wek.back()]-poz[i] ); kon[wek.back()]=bsa-1; } if (wek.empty()) { pocz[i]=1; kon[i]=n; wek.push_back(i); } else { if (kon[wek.back()]<n) { pocz[i]=kon[wek.back()]+1; kon[i]=n; wek.push_back(i); } } printf("%lld\n", wyn); } return 0; } |