// PA2015, runda 1, Siano // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include <cassert> using namespace std; int N, M; int main() { scanf("%d%d", &N, &M); vector<int> A(N); for (auto &a:A) { scanf("%d", &a); } sort(A.begin(), A.end()); vector<long long> S(N+1); S[0]=0; for (int i=0; i<N; i++) { S[i+1]=S[i]+A[i]; } vector<pair<pair<long long,long long>, int> > D(M); // t, h, i int top=1; D[0]=make_pair(make_pair(0LL, 0LL), 0); while (M--) { long long t, h, res=0; int i1=N; scanf ("%lld%lld", &t, &h); long long t0 = D[top-1].first.first; long long h0 = D[top-1].first.second; int i0 = D[top-1].second; // assert((t-t0) * A.back() + h0 <= 1000000000000LL); // assert((t-t0) * A.back() + h0 >= 0LL); if ((t-t0) * A.back() + h0 <= h) { printf("0\n"); continue; } while (top>1){ long long t0 = D[top-1].first.first; long long h0 = D[top-1].first.second; long long i0 = D[top-1].second; if ((t-t0) * A[i0] < h - h0) break; res += (S[i1]-S[i0])*(t-t0)+(i1-i0)*(h0-h); i1=i0; top--; } t0 = D[top-1].first.first; h0 = D[top-1].first.second; i0 = D[top-1].second; // assert(h - h0 + t -t0 -1 >=0); // assert(t-t0 > 0); int i = lower_bound(A.begin()+i0, A.begin()+i1, (h - h0 + t -t0 -1)/(t-t0)) - A.begin(); res+=(S[i1]-S[i])*(t-t0)+(i1-i)*(h0-h); D[top++]=make_pair(make_pair(t, h), i); 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 | // PA2015, runda 1, Siano // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include <cassert> using namespace std; int N, M; int main() { scanf("%d%d", &N, &M); vector<int> A(N); for (auto &a:A) { scanf("%d", &a); } sort(A.begin(), A.end()); vector<long long> S(N+1); S[0]=0; for (int i=0; i<N; i++) { S[i+1]=S[i]+A[i]; } vector<pair<pair<long long,long long>, int> > D(M); // t, h, i int top=1; D[0]=make_pair(make_pair(0LL, 0LL), 0); while (M--) { long long t, h, res=0; int i1=N; scanf ("%lld%lld", &t, &h); long long t0 = D[top-1].first.first; long long h0 = D[top-1].first.second; int i0 = D[top-1].second; // assert((t-t0) * A.back() + h0 <= 1000000000000LL); // assert((t-t0) * A.back() + h0 >= 0LL); if ((t-t0) * A.back() + h0 <= h) { printf("0\n"); continue; } while (top>1){ long long t0 = D[top-1].first.first; long long h0 = D[top-1].first.second; long long i0 = D[top-1].second; if ((t-t0) * A[i0] < h - h0) break; res += (S[i1]-S[i0])*(t-t0)+(i1-i0)*(h0-h); i1=i0; top--; } t0 = D[top-1].first.first; h0 = D[top-1].first.second; i0 = D[top-1].second; // assert(h - h0 + t -t0 -1 >=0); // assert(t-t0 > 0); int i = lower_bound(A.begin()+i0, A.begin()+i1, (h - h0 + t -t0 -1)/(t-t0)) - A.begin(); res+=(S[i1]-S[i])*(t-t0)+(i1-i)*(h0-h); D[top++]=make_pair(make_pair(t, h), i); printf("%lld\n", res); } return 0; } |