#include<bits/stdc++.h> using namespace std; int n, m, a, pam=0, L, S, P; long long wynik; pair <long long, long long> p[200005]; int main() { scanf("%d%d", &n, &m); for(int i=0; i<n; i++) { scanf("%d", &a); p[i].first=(long long)(a-pam); pam=a; } sort(p, p+n); p[0].second=p[0].first; for(int i=0; i<n-1; i++) { p[i+1].second=p[i].second+p[i+1].first; } for(int i=0; i<m; i++) { scanf("%d", &a); L=0; P=n-1; while(L!=P) { S=(L+P)/2; if(p[S].first>(long long)a) { P=S; } else { L=S+1; } } wynik=((long long)L*a)-p[L-1].second; printf("%lld\n", wynik); } 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 | #include<bits/stdc++.h> using namespace std; int n, m, a, pam=0, L, S, P; long long wynik; pair <long long, long long> p[200005]; int main() { scanf("%d%d", &n, &m); for(int i=0; i<n; i++) { scanf("%d", &a); p[i].first=(long long)(a-pam); pam=a; } sort(p, p+n); p[0].second=p[0].first; for(int i=0; i<n-1; i++) { p[i+1].second=p[i].second+p[i+1].first; } for(int i=0; i<m; i++) { scanf("%d", &a); L=0; P=n-1; while(L!=P) { S=(L+P)/2; if(p[S].first>(long long)a) { P=S; } else { L=S+1; } } wynik=((long long)L*a)-p[L-1].second; printf("%lld\n", wynik); } return 0; } |