#include <bits/stdc++.h> using namespace std; const int N = 500005; int n, m, cSize; int growth[N]; long long pref[N], day[N], cutHeight[N]; pair<int, int> cutStack[N]; inline bool willBeCut(int w, int lastQueryId, int queryId) { long long newHeight = cutHeight[lastQueryId] + (day[queryId] - day[lastQueryId]) * growth[w]; return newHeight >= cutHeight[queryId]; } int firstCut(int queryId, int low, int high) { int ret = high + 1; while (low <= high) { int mid = (low + high) / 2; if (willBeCut(mid, cutStack[cSize].first, queryId)) { ret = mid; high = mid - 1; } else { low = mid + 1; } } return ret; } inline long long cutGrass(int firstPos, int lastPos, int lastQueryId, int queryId) { return (pref[lastPos] - pref[firstPos - 1]) * (day[queryId] - day[lastQueryId]) + (cutHeight[lastQueryId] - cutHeight[queryId]) * (lastPos - firstPos + 1); } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &growth[i]); } sort(growth + 1, growth + 1 + n); for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + growth[i]; } cutStack[++cSize] = make_pair(0, 0); for (int i = 1; i <= m; i++) { scanf("%lld %lld", &day[i], &cutHeight[i]); int last = n + 1; long long hay = 0; while (cSize > 0 && willBeCut(cutStack[cSize].second, cutStack[cSize].first, i)) { hay += cutGrass(cutStack[cSize].second, last - 1, cutStack[cSize].first, i); last = cutStack[cSize].second; cSize--; } int first = cutStack[cSize].second + 1; int firstCutPosition = firstCut(i, first, last - 1); hay += cutGrass(firstCutPosition, last - 1, cutStack[cSize].first, i); if (firstCutPosition != n + 1) { cutStack[++cSize] = make_pair(i, firstCutPosition); } printf("%lld\n", hay); } 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 | #include <bits/stdc++.h> using namespace std; const int N = 500005; int n, m, cSize; int growth[N]; long long pref[N], day[N], cutHeight[N]; pair<int, int> cutStack[N]; inline bool willBeCut(int w, int lastQueryId, int queryId) { long long newHeight = cutHeight[lastQueryId] + (day[queryId] - day[lastQueryId]) * growth[w]; return newHeight >= cutHeight[queryId]; } int firstCut(int queryId, int low, int high) { int ret = high + 1; while (low <= high) { int mid = (low + high) / 2; if (willBeCut(mid, cutStack[cSize].first, queryId)) { ret = mid; high = mid - 1; } else { low = mid + 1; } } return ret; } inline long long cutGrass(int firstPos, int lastPos, int lastQueryId, int queryId) { return (pref[lastPos] - pref[firstPos - 1]) * (day[queryId] - day[lastQueryId]) + (cutHeight[lastQueryId] - cutHeight[queryId]) * (lastPos - firstPos + 1); } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &growth[i]); } sort(growth + 1, growth + 1 + n); for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + growth[i]; } cutStack[++cSize] = make_pair(0, 0); for (int i = 1; i <= m; i++) { scanf("%lld %lld", &day[i], &cutHeight[i]); int last = n + 1; long long hay = 0; while (cSize > 0 && willBeCut(cutStack[cSize].second, cutStack[cSize].first, i)) { hay += cutGrass(cutStack[cSize].second, last - 1, cutStack[cSize].first, i); last = cutStack[cSize].second; cSize--; } int first = cutStack[cSize].second + 1; int firstCutPosition = firstCut(i, first, last - 1); hay += cutGrass(firstCutPosition, last - 1, cutStack[cSize].first, i); if (firstCutPosition != n + 1) { cutStack[++cSize] = make_pair(i, firstCutPosition); } printf("%lld\n", hay); } return 0; } |